footnote

# Rethinking the Promotion Brought by Contrastive Learning
to Semi-Supervised Node Classification

Deli Chen1, Yankai Lin1, Lei Li2, Xuancheng Ren2, Peng Li3, Jie Zhou1, Xu Sun2
1Pattern Recognition Center, WeChat AI, Tencent Inc., China
2MOE Key Lab of Computational Linguistics, School of Computer Science, Peking
University, China
3Institute for AI Industry Research (AIR), Tsinghua University, China
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Graph Contrastive Learning (GCL) has proven highly effective in promoting the
performance of Semi-Supervised Node Classification (SSNC). However, existing
GCL methods are generally transferred from other fields like CV or NLP, whose
underlying working mechanism remains under-explored. In this work, we first
deeply probe the working mechanism of GCL in SSNC, and find that the promotion
brought by GCL is severely unevenly distributed: the improvement mainly comes
from subgraphs with less annotated information, which is fundamentally
different from contrastive learning in other fields. However, existing GCL
methods generally ignore this uneven distribution of annotated information and
apply GCL evenly to the whole graph. To remedy this issue and further improve
GCL in SSNC, we propose the Topology InFormation gain-Aware Graph Contrastive
Learning (TIFA-GCL) framework that considers the annotated information
distribution across graph in GCL. Extensive experiments on six benchmark graph
datasets, including the enormous OGB-Products graph, show that TIFA-GCL can
bring a larger improvement than existing GCL methods in both transductive and
inductive settings. Further experiments demonstrate the generalizability and
interpretability of TIFA-GCL.111Part of the work was done while Peng Li was
working at Tencent.

Figure 1:  The RADIAL DECAY phenomenon in semi-supervised node classification
task. Information Intensity Ranking and Information Clarity Ranking are the
node ranking orders of annotated information intensity (Eq. 2) and clarity
(Eq. 3) from the highest to lowest, respectively. Subfigure (a) displays the
prediction result of GCN model on CORA dataset. We can find that graph nodes
in SSNC are characterized by a fan-shaped distribution and the GNN’s inference
ability decays radially outward. Subfigure (b) displays the error rate for
different grids in subfigure (a). Subfigure (c) displays the contribution of
GCL (gap with GNN) among different grids. We can find that the GCL effect
increases radially outward, which is contrary to GNN’s learning ability.

##  1 Introduction

Graph Neural Networks (GNNs) can effectively utilize the relation of nodes
from graph and have shown powerful modeling capabilities Yang et al. (2016) in
Semi-Supervised Node Classification (SSNC). Nevertheless, vanilla GNN training
Kipf and Welling (2017) accesses the training signal mainly from the limited
labeled nodes and pays little attention to the massive information contained
in the unlabeled nodes. To fix this issue, recent studies Hassani and
Khasahmadi (2020); Zhu et al. (2020, 2021); You et al. (2020); Wan et al.
(2021); Feng et al. (2020) introduce Contrastive Learning (CL) into graph
scene to leverage the information of the unlabeled nodes and have achieved
promising performance.

Though successful, the working mechanism of Graph Contrastive Learning (GCL)
in SSNC remains under-explored because the graph scene is fundamentally
different from the other scenes like image or text. The samples are connected
by complex edges and the task-related annotated information are propagated
from the labeled nodes to the unlabeled nodes through graph topology, which
results in an imbalanced distribution of the annotated information
distribution across the graph. Therefore, how this imbalanced distribution can
affect GCL running and why CL works in the SSNC task have become essential
research questions in this field.

In this work, we first investigate how the annotated information distribution
affects the GCL effect. We employ the well-known Label Propagation Buchnik and
Cohen (2018) method to measure the annotated information distribution. We find
that the promotion of GCL mainly comes from those nodes with less annotated
information. Specifically, in Figure 1, we notice that GNN’s inference ability
decays radially outward in the annotated information intensity-clarity
coordinate system, while GCL’s effect, in contrast, increases radially
outward. However, existing GCL methods overlook this phenomena and apply CL to
the whole graph evenly.

Motivated by our findings, we propose the Topology InFormation gain–Aware
Graph Contrastive Learning (TIFA-GCL) framework to enhance the GCL methods
from two aspects: (1) from the global view of the whole graph, we enhance the
GCL effect on nodes that receive less annotated information from the
information source (labeled nodes), by devising novel self-adaptive graph
corruption and CL loss weight schedule mechanisms; and (2) from the local view
of each node, we observe that nodes with similar annotated information
distribution are more likely to share the same class label, based on which we
promote the contrastive pair sampling and subgraph sampling strategies.

Extensive experiments on six benchmark datasets, including the enormous OGB-
Products graph Hu et al. (2020), have shown that our TIFA-GCL method can bring
more significant improvements to GNN training compared to existing GCL methods
in both transductive and inductive setting. Further investigations are
provided to answer several important research questions of our work.

##  2 A Closer Look at GCL in Semi-Supervised Node Classification

Owing to the success of GCL in SSNC, we attempt to probe its working mechanism
in this section. Since nodes’ received annotated information has a crucial
impact on GNN’s inference performance, we first introduce our measurement for
the node’s received annotated information from the labeled nodes along graph
topology, and then investigate how the annotated information will affect the
performance of GCL from the perspectives of information intensity and clarity.

###  2.1 Task Formalization

We follow the benchmark setting Kipf and Welling (2017); Yang et al. (2016);
Hamilton et al. (2017) to discuss the working mechanism of GCL in the semi-
supervised node classification task. Formally, given an undirected graph
$\mathcal{G}=(\mathcal{\bm{V}},\mathcal{\bm{E}})$, where $\mathcal{\bm{V}}$ is
the node set with an embedding matrix $\bm{X}\in\mathbb{R}^{n\times h}$
($n=|\mathcal{\bm{V}}|$ , $h$ is the feature dimension size) and
$\mathcal{\bm{E}}$ is the edge set represented by an adjacency matrix
$\bm{A}\in\mathbb{R}^{n\times n}$, the node classification task aims to learn
a classifier $\mathcal{F}$ to predict the class label $\bm{y}$ for each node.
We denote the labeled and unlabeled node sets as $\bm{{L}}$ and $\bm{{U}}$,
respectively.

###  2.2 Measuring the Annotated Information from the Labeled Nodes

In this work, we employ the Label Propagation Buchnik and Cohen (2018) (LP)
algorithm to measure the annotated information distribution among the graph
nodes that have complex connections with graph edges. LP is a very popular
method for SSNC based on the message-passing mechanism: the labels are
propagated from the labeled nodes to the unlabeled nodes through graph edges.
We adopt LP to measure the annotated information distribution for two reasons:
(1) LP focuses on the graph topology, which can reflect the annotated
information clearly; (2) LP shares the same mechanism (message-passing) with
many GNN models Wang and Leskovec (2020), so the conclusions of it can be
transferred to general GNN models like GCN Kipf and Welling (2017) and
GraphSAGE Hamilton et al. (2017). The LP method can be formulated as:

$\bm{Z}=\alpha(\bm{I}-(1-\alpha)\bm{A^{\prime}})^{-1}\bm{Z}^{0},$ (1)

$\bm{I}$ is the identity matrix; $\alpha\in(0,1]$ represents the random walk
restart probability. $\bm{A^{\prime}}=\bm{A}\bm{D^{-1}}$ and $\bm{D}$ is the
node degree matrix. $\bm{Z}\in\mathbb{R}^{n\ast k}$ is the convergence result
of LP; $\bm{Z}_{i,j}$ indicates the probability that the the $i$-th node is
belong to the $j$-th class and we regard it as the influence received by the
$i$-th node from the $j$-th class’s labeled nodes; $\bm{Z}^{0}$ in the initial
label matrix where labeled nodes are represented by one-hot vectors and
unlabeled nodes are filled with zero. In practice, we take a updated version
$\bm{Z}^{\ast}$ to consider the category preference of nodes (shown in
Appendix A1).

###  2.3 Probing the Mechanism of GCL

In this part, we analyze the working mechanism of GCL with the help of LP.
Ideally, the received information for each node should be concentrated on one
category, which means that the annotated information is strong and clear. So
we regard the maximum item of vector $\bm{Z}_{i,:}^{\ast}$ to be the
information intensity and the gap to the others as the information clarity for
node $i$:

$\displaystyle\bm{Q}_{i}^{\text{Intensity}}$
$\displaystyle=\mathrm{max}(\bm{Z}_{i,:}^{\ast})$ (2)
$\displaystyle\bm{Q}_{i}^{\text{Clarity}}$
$\displaystyle=\mathrm{max}(\bm{Z}_{i,:}^{\ast})-\sum\bm{Z}_{i,:}^{\ast}$ (3)

where $\mathrm{max}(\cdot)$ returns the max value of the input vector. With
$\bm{Q}^{\text{Intensity}}$ and $\bm{Q}^{\text{Clarity}}$, we conduct an
analysis experiment on the benchmark CORA Sen et al. (2008) dataset trained by
GCN Kipf and Welling (2017) in Figure 1. We plot the prediction results in the
$\bm{Q}^{\text{Intensity}}\times\bm{Q}^{\text{Clarity}}$ rectangular
coordinate system in Figure 1 (a). Figure 1 (b) shows the error rates for
different grids from Figure 1 (a). From Figure 1 (a)(b), we can find that, the
graph nodes in SSNC are distributed in a fan shape, which means that there is
no nodes with low $\bm{Q}^{\text{Intensity}}$ and low
$\bm{Q}^{\text{Clarity}}$ at the same time. Moreover, we notice that the GNN’s
inference ability has the characteristic of radial decay222 This phenomenon
can also be found in other datasets. We provide the results in Appendix A2.:
GNN can predict accurately for nodes around the origin of coordinate, which
have both high $\bm{Q}^{\text{Intensity}}$ and high $\bm{Q}^{\text{Clarity}}$;
however, the GNN inference ability decays radially outward from the origin of
coordinate, where nodes receive more noise (information from other classes’
labeled nodes) and less helpful information. Figure 1 (c) displays the
contribution of GCL effect (the improvement to GNN) among all the grids from
Figure 1 (a). We can find that just in contrary to GNN’s inference ability,
GCL’s effect has the characteristic of radial increase: the farther the sector
away from the origin of the coordinate, the greater the improvement brought by
GCL. Besides, comparing to nodes with high $\bm{Q}^{\text{Intensity}}$ and low
$\bm{Q}^{\text{Clarity}}$ (upper left in plot), GCL enhances GNN’s learning
ability for nodes with low $\bm{Q}^{\text{Intensity}}$ and high
$\bm{Q}^{\text{Clarity}}$ (low right in plot) more effectively. We analyze the
reason lies in that nodes with high $\bm{Q}^{\text{Intensity}}$ and low
$\bm{Q}^{\text{Clarity}}$ are strongly influenced by graph learning and can be
hardly corrected by CL.

Inspired by the fan-shaped distribution of graph nodes and the radical decay
phenomenon in GNN, we quantitatively measure each node’s Topology Information
Gain (short as TIG, indicating the quality of nodes’ received annotated
information in this work) by jointly considering the node information
intensity and clarity. The TIG value $\bm{T}_{i}$ for the $i$-th node is
calculated in the following equation:

$\displaystyle\bm{T}_{i}=\bm{Q}_{i}^{\text{Intensity}}+\frac{\lambda}{k-1}\ast\bm{Q}_{i}^{\text{Clarity}},$
(4)

where $\lambda$ is the weight of information clarity. The GCL effect across
TIG bins is shown in Appendix A3. We summary that: The promotion of GCL mainly
comes from nodes with less annotated information in the SSNC task.

##  3 Methodology

In this section, we first introduce the whole framework of our method in
Section 3.1, and then introduce how we modify the CL loss accumulation
(Section 3.2), graph perturbation (Section 3.3) and contrastive pair sampling
(Section 3.4) to consider the annotated information distribution and promote
the CL effect. Moreover, a novel subgraph sampling (shown in Appendix B2)
method called SAINT-TIFA is proposed for the inductive setting.

###  3.1 TIFA-GCL Framework

Generally, in semi-supervised GCL, the training objective consists of two
parts: the supervised cross-entropy loss and the unsupervised contrastive
loss. Given a GNN encoder $\mathcal{F}$ (e.g., GCN), the supervised cross-
entropy loss $\mathcal{L}_{CE}$ is calculated on the labeled set $\bm{{L}}$:

$\displaystyle\bm{g}$ $\displaystyle=\mathcal{F}(\bm{X},\bm{A},\bm{\theta}),$
(5) $\displaystyle\mathcal{L}_{CE}$
$\displaystyle=-\frac{1}{|\bm{{L}}|}\sum_{i\in\bm{{L}}}\sum_{c=0}^{k-1}\bm{y}^{c}_{i}\,\log\,\,{\bm{g}}^{c}_{i},$
(6)

where $\bm{g}_{i}$ is the GNN output for node $i$; $\bm{y}_{i}$ is the gold
label in one-hot embedding; $\bm{\theta}$ is the parameters of $\mathcal{F}$.
Apart from $\mathcal{L}_{CE}$, the contrastive loss in TIFA-GCL contains two
parts: the self-consistency loss and the pair-wise loss with positive and
negative pairs. The self-consistency loss is calculated in the following
equation:

$\displaystyle\mathcal{L}^{i}_{s}$
$\displaystyle=\mathrm{KL}(\mathcal{F}(\bm{X_{p}},\bm{A_{p}},\bm{{\theta}})_{i},\mathcal{F}(\bm{X},\bm{A},\bm{\widetilde{\theta}})_{i}),$
(7)

where $\mathrm{KL(\cdot,\cdot)}$ is the Kullback-Leibler divergence function;
the augmented node embedding matrix $\bm{X_{p}}$ and the adjacency matrix
$\bm{A_{p}}$ are generated by the TIFA-graph perturbation which is detailed in
Section 3.3. Following Xie et al. (2021) and Wang et al. (2020),
$\bm{\widetilde{\theta}}$ is a fixed copy of the current parameter
$\bm{{\theta}}$ and the gradient is not propagated through
$\bm{\widetilde{\theta}}$. Similarly, the contrastive loss with positive and
negative pairs are computed:

$\displaystyle\mathcal{L}^{i}_{p}=$
$\displaystyle\frac{1}{|\bm{P}_{i}|}\sum_{j\in\bm{P}_{i}}\mathrm{KL}(\mathcal{F}(\bm{X_{p}},\bm{A_{p}},\bm{{\theta}})_{i},\mathcal{F}(\bm{X},\bm{A},\bm{\widetilde{\theta}})_{j})$
$\displaystyle-\,\mu_{1}$
$\displaystyle\frac{1}{|\bm{N}_{i}|}\sum_{j\in\bm{N}_{i}}\mathrm{KL}(\mathcal{F}(\bm{X_{p}},\bm{A_{p}},\bm{{\theta}})_{i},\mathcal{F}(\bm{X},\bm{A},\bm{\widetilde{\theta}})_{j}),$
(8)

where $\bm{P}_{i}$ and $\bm{N}_{i}$ are the positive and negative pairs for
the $i$-th node generated by our TIFA-contrastive pair sampling strategy
introduced in Section 3.4, $\mu_{1}$ is a hyper-parameters to control the
weight of GCL loss of negative pairs comparing to positive pairs. Then the
complete unsupervised loss on node $i$ is calculated via:

$\mathcal{L}_{U}^{i}=\mathcal{L}^{i}_{s}+\mu_{2}\mathcal{L}_{p}^{i},$ (9)

where $\mu_{2}$ controls the weight of $\mathcal{L}_{p}^{i}$ relative to
$\mathcal{L}_{s}^{i}$.

###  3.2 TIFA-Contrastive Loss Weight Schedule

Different from all the existing GCL studies Zhu et al. (2020); Wan et al.
(2021); Wang et al. (2020); Zhu et al. (2021); Hassani and Khasahmadi (2020);
You et al. (2020); Feng et al. (2020), which accumulate the unsupervised
contrastive loss from different nodes directly, we instead propose to adjust
the CL loss weight adaptively among different subgraphs according to their
TIG. Specifically, we set the CL weight $\bm{w}_{i}$ of each node differently
using a cosine annealing schedule based on the node TIG ranking333We also try
other schedule methods like linear schedule, piece-wise schedule and
scheduling based on the absolute TIG value instead of the relative ranking.
The experiment results show the cosine method works best.:

$\displaystyle\bm{w}_{i}=w_{\text{min}}+\frac{1}{2}(w_{\text{max}}-w_{\text{min}})(1+\mathrm{cos}(\frac{\mathrm{Rank}(\bm{T}_{i})}{n}\pi)),$
(10)

where $w_{\text{min}},w_{\text{max}}$ are the hyper-parameters indicating the
minimum and the maximum values of CL loss, respectively;
${\mathrm{Rank}}(\bm{T}_{i})$ is the ranking order of $\bm{T}_{i}$ from the
smallest to the largest. Then the final training objective of TIFA-GCL
consists of the supervised loss and a weighted-sum of the unsupervised
contrastive loss:

$\mathcal{L}=\mathcal{L}_{CE}+\frac{1}{n}\sum\nolimits_{i=0}^{n-1}\bm{w}_{i}\mathcal{L}^{i}_{U},$
(11)

With this manner, subgraphs receiving less annotated information from graph
topology can benefit more from GCL, forming a more adaptive combination of
graph representation learning and graph contrastive learning.

###  3.3 TIFA-Graph Perturbation

Unlike perturbation in images He et al. (2020); Sohn et al. (2020) where
samples can be perturbed independently, graph nodes interact with each other
and the disturbance of one node will spread to its adjacent neighbors.
Therefore, if we perturb too many nodes or edges in graph, the augmented graph
will be too different from the original one and thus weakening the GCL effect.
We propose that the limited graph perturbation should be more likely to take
place on subgraphs with insufficient information gain from graph learning.
Thus, we propose to sample nodes to disturb according to their TIG values: a
node will be selected with a higher probability for augmentation when it has a
lower TIG value. Comparing to the contrastive loss weight schedule which
directly adjusts the CL weight, weighted graph perturbation is a more
essential method to enhance GCL effect on nodes with fewer TIG values since
graph perturbation is the upstream operation of computing CL target. The
details of TIFA-graph perturbation algorithm is shown in Appendix B1.

Figure 2: The intra-class node-pair ratio across the global topology distance
(Eq. 12) ranking bin from the smallest to the largest (CORA dataset). Neighbor
represents this ratio in all neighborhood node-pairs; All represents this
ratio in all possible node-pairs.

###  3.4 TIFA-Contrastive Pair Sampling

Contrastive pair sampling, especially the negative pair sampling, has a
crucial impact on CL Robinson et al. (2021); Yang et al. (2020). Different
from existing works which simply regard all other nodes Wang et al. (2020);
Zhu et al. (2020) or labeled nodes from other class Wan et al. (2021) as
negative samples, we propose to sample contrastive pairs based on the relative
distance between nodes.

We observe that (Figure 2) nodes with similar annotated information
distribution are more likely to share the same class label with each other,
and vice versa. Therefore, our measurement for the node relative distance
mainly depends on the difference of node LP result, which contains both the
global topology information and annotated information. Specifically, we
normalize the each node’s LP vector and then calculate the KL divergence
between nodes as the global topology distance:

$\bm{D}^{g}_{i,j}=\mathrm{KL}(\bm{p}_{i},\bm{p}_{j}),\quad\quad\bm{p}_{i}=\mathrm{softmax}(\bm{Z}^{\ast}),$
(12)

where $\mathrm{softmax}(\cdot)$ function is adopted to transfer the original
LP matrix $(\bm{Z}^{\ast})$ into a probability distribution over all the
categories. Besides, we supplement the relative distance measuring from the
view of local topology distance and the node embedding distance. For local
topology distance $\bm{D}^{l}_{i,j}$, we use the minimum jump hop number as an
indicator. For node embedding distance $\bm{D}^{e}_{i,j}$, we calculate the
cosine distance between the nodes in embedding $\bm{X}$. The final node
relative distance is calculated by the weighted sum of the global/local
topology distance and the node embedding distance:

$\bm{D}_{i,j}={\rm S}(\bm{D}^{g}_{i,j})+\lambda_{1}{\rm
S}(\bm{D}^{l}_{i,j})+\lambda_{2}{\rm S}(\bm{D}^{e}_{i,j}),$ (13)

where $\lambda_{1},\lambda_{2}$ is the weight of the two supplement items;
${\rm S(\cdot)}$ represents the scale operation to transfer the original value
to $[0,1]$. Then we construct positive and negative pairs for each node
individually. For the $i$-th node (anchor node), the positive set $\bm{P}_{i}$
is composed of the closest nodes with the smallest relative distance; for the
negative set $\bm{N}_{i}$, we propose to take the semi-difficult nodes Schroff
et al. (2015) which are neither too far or too close to the anchor node. Given
the personally ranked node list $\bm{R}_{i}$ sorted by $\bm{D}_{i}$ from the
smallest to the largest (the $i$-th node itself is excluded), $\bm{P}_{i}$ and
$\bm{N}_{i}$ are truncated from $\bm{R}_{i}$, respectively:

$\bm{P}_{i}=\bm{R}_{i}[0:\mathrm{post}_{end}],\,\bm{N}_{i}=\bm{R}_{i}[\mathrm{negt}_{beg}:\mathrm{negt}_{end}],$
(14)

where $\mathrm{post}_{end}$ is the end index for positive set;
$\mathrm{negt}_{beg}$ and $\mathrm{negt}_{end}$ are the begin and end indexes
for negative set.

##  4 Experiments

In this section, we first give a brief introduction to the experiment datasets
and settings. Followingly, we show the effectiveness of the proposed TIFA-GCL
method by comparing with both advanced GNN models and other GCL methods in
both transductive and inductive settings.

###  4.1 Datasets and Experimental Settings

We conduct experiments on six widely-used graph datasets, namely paper
citations networks Sen et al. (2008) (CORA,CiteSeer and Pubmed; these three
datasets are the mostly-used benchmark networks Yang et al. (2016); Kipf and
Welling (2017); Veličković et al. (2018) in the SSNC studies), Amazon Co-
purchase networks Shchur et al. (2018) (Photo and Computers) and the enormous
OGB-Products graph Hu et al. (2020). More details about the datasets,
experiment settings and hyper-parameters can be found in Appendix C.

###  4.2 Overall Results

The overall results of our proposed methods in transductive and inductive
setting are shown in Table 1 and 2, respectively. For the transductive
experiments, we set two lines of baselines to verify the effectiveness of our
method:(1) Popular GNN models, including GCN Kipf and Welling (2017), GAT
Veličković et al. (2018), GraphSAGE Hamilton et al. (2017) and GraphMix Verma
et al. (2019); (2) Existing GCL methods which apply CL to graph uniformly
(uniform-GCL), including GRACE Zhu et al. (2020), NodeAug Wang et al. (2020),
MultiView Hassani and Khasahmadi (2020) and GraphCL You et al. (2020). The
transductive results are shown in Table 1. We can find that: (1) Methods with
GCL modules (middle 4 models) generally outperform methods without GCL modules
(top 4 models), since they can leverage the information from a large number of
unsupervised nodes by comparing the perturbed representations. (2) Our TIFA-
GCL can further improve the GCL effect in SSNC than uniform-GCL methods by
considering the received annotated information of different nodes.

For the inductive training, we conduct experiments to verify the effect of
both TIFA-GCL framework and SAINT-TIFA subgraph sampling method. In Table 2,
we display results of different combinations of GNN aggregators, contrastive
methods, and subgraph sampling methods (Full-batch, Neighbor Hamilton et al.
(2017), SAINT-RW Zeng et al. (2020) and the proposed SAINT-TIFA). We find that
for both GAT and GraphSAGE444As shown in Table 2, GCN performs worse than GAT
and GraphSAGE, so we don’t experiment on it. The same reason not to experiment
with Neighbor Sampling in GCL., TIFA-GCL can bring larger improvement for GNN
training compared to uniform-GCL555The uniform-GCL’s performance here is based
on our model’s ablation version which replaces all the TIFA modules with the
uniform ones from GRACE Zhu et al. (2020). The same below., which verifies the
effectiveness of TIFA-GCL for inductive learning on enormous graphs. Moreover,
our SAINT-TIFA subgraph sampling method outperforms the SAINT-RW method for
both GAT and GraphSAGE, proving that making nodes more likely to interact with
high-affinity neighbors can further benefit inductive graph training.

Method | CORA | CiteSeer | PubMed | Photo | Comp.
---|---|---|---|---|---
GCN | 81.0$\pm$0.7 | 69.1$\pm$0.8 | 76.8$\pm$0.8 | 88.0$\pm$1.7 | 80.7$\pm$0.7
GAT | 79.9$\pm$2.1 | 69.6$\pm$1.4 | 77.2$\pm$1.0 | 88.7$\pm$1.9 | 77.9$\pm$2.1
GraphSAGE | 80.7$\pm$1.2 | 67.8$\pm$1.4 | 76.3$\pm$0.6 | 87.7$\pm$1.2 | 79.6$\pm$1.2
GraphMix | 81.5$\pm$0.9 | 69.3$\pm$0.4 | 78.0$\pm$1.3 | 89.5$\pm$1.7 | 81.2$\pm$2.7
GRACE | 82.1$\pm$1.6 | 70.3$\pm$1.5 | 77.8$\pm$1.8 | 89.3$\pm$1.3 | 82.1$\pm$1.5
NodeAug | 82.7$\pm$1.3 | 71.1$\pm$1.2 | 78.4$\pm$0.7 | 89.7$\pm$1.8 | 83.0$\pm$1.9
MultiView | 81.8$\pm$0.8 | 71.5$\pm$1.7 | 77.9$\pm$0.1 | 88.9$\pm$1.5 | 82.8$\pm$2.0
GraphCL | 82.4$\pm$1.1 | 70.8$\pm$0.6 | 78.2$\pm$0.5 | 90.3$\pm$2.3 | 83.2$\pm$0.7
TIFA-GCL |  83.6$\pm$0.8 |  72.5$\pm$0.6 |  79.2$\pm$0.6 |  91.0$\pm$0.6 |  83.6$\pm$1.4

Table 1: Empirical results (classification accuracy%) of graph transductive
learning. The top four methods are typical GNN models without a GCL mechanism,
and the middle four methods are uniform-GCL methods.

###  4.3 Generalizability of TIFA-GCL

Our TIFA-GCL method is model-agnostic and thus can be applied to any GNN
encoders. To verify the generalizability of TIFA-GCL, we evaluate the
performance of our TIFA-GCL with multiple GNN architectures and different
labeling sizes. As shown in Figure 3, we conduct experiments on 8 different
GNN models: GCN Kipf and Welling (2017), GAT Veličković et al. (2018),
GraphSAGE Hamilton et al. (2017), HyperGraph Bai et al. (2021), ChebConv
Defferrard et al. (2016), StandGraph Morris et al. (2019), ARMA Bianchi et al.
(2019) and Feast Verma et al. (2018). We find similar patterns in other
datasets and thus only display the result of CORA due to the space limit. We
find that, although these GNNs vary greatly in architectures, TIFA-GCL can
consistently promote the GNN performance comparing to uniform-GCL under
different labeling sizes, proving the effectiveness of TIFA-GCL in the broader
SSNC scenarios. We also find that the improvement of TIFA-GCL is more
significant when the labeling size is small. In such case, the annotated
information is sparse and the importance of supplementary information from
contrastive learning increases; thus our method is suitable for these scenes
where few annotated data is available.

Aggregator | Sampling | Contrastive | Test Acc(%)
---|---|---|---
MLP* | N/A | No | 61.1$\pm$0.1
Node2vec* | N/A | No | 72.5$\pm$0.1
GCN* | Full-batch | No | 75.6$\pm$0.2
GraphSAGE* | Full-batch | No | 78.5$\pm$0.1
GraphSAGE | Neighbor | No | 78.9$\pm$0.1
SAINT-RW | No | 79.3$\pm$0.2
uniform-GCL | 79.8$\pm$0.4
TIFA-GCL | 80.1$\pm$0.4
SAINT-TIFA | TIFA-GCL |  80.7$\pm$0.3
GAT | Neighbor | No | 79.8$\pm$0.4
SAINT-RW | No | 80.0$\pm$0.4
uniform-GCL | 81.1$\pm$0.1
TIFA-GCL | 82.1$\pm$0.3
SAINT-TIFA | TIFA-GCL |  82.5$\pm$0.5

Table 2: Empirical results (classification accuracy%) of inductive learning on
OGB-Products dataset. $\ast$ indicates that the result are taken from the OGB
official results. Figure 3: The performance of TIFA-GCL on multiple base GNN
backbones under different labeling size (5/10/20 labeled nodes in each
category) on the CORA dataset.

###  4.4 Ablation Study

To verify the contributions of different modules in TIFA-GCL, we conduct
ablation studies in this part. Table 3 shows the performance of the model
variants when removing the loss weight schedule from Section 3.2, or replacing
the graph perturbation from Section 3.3 and the pair sampling modules from
Section 3.4 with the uniform one from GRACE Zhu et al. (2020). From Table 3,
we find that when removing or replacing any one of three modules, the results
of our model variants across three datasets all decrease, which verifies the
effectiveness of them. We can also find that the TIFA-graph perturbation
brings the largest improvement to the results; it is because that the strength
of disturbance directly influences the GCL’s effect and our TIFA-graph
perturbation can provide intense contrastive information for subgraphs that
needs supplementary information most. Moreover, the results of these variants
still outperform the the GCN and GRACE models, which demonstrates the overall
advantage of the TIG-adaptive mechanisms in our approach.

Method | CORA | CiteSeer | PubMed
---|---|---|---
GCN | 81.0$\pm$0.7 | 69.1$\pm$0.8 | 76.8$\pm$0.8
GRACE | 82.1$\pm$1.6 | 70.3$\pm$1.5 | 77.8$\pm$1.8
Full TIFA-GCL | 83.6$\pm$0.8 | 72.5$\pm$0.6 | 79.2$\pm$0.6
$w/o$ TIFA-CL Schedule | 82.7$\pm$1.3 ($\downarrow 0.9$) | 72.1$\pm$0.6 ($\downarrow 0.4$) | 78.7$\pm$0.7 ($\downarrow 0.5$)
$r/p$ TIFA-Perturbation | 82.8$\pm$0.9 ($\downarrow 0.8$) | 71.2$\pm$1.2 ($\downarrow 1.3$) | 78.5$\pm$1.1 ($\downarrow 0.7$)
$r/p$ TIFA-Pair Sampling | 83.1$\pm$1.3 ($\downarrow 0.5$) | 71.8$\pm$0.5 ($\downarrow 0.7$) | 78.7$\pm$0.7 ($\downarrow 0.5$)

Table 3: Ablation results (classification accuracy %) of the three TIFA
modules in TIFA-GCL. $w/o$ denotes removing the module and $r/p$ denotes
replacing the module with the uniform one in GRACE.

##  5 Analysis

In this section, we provide in-depth analyses of our proposal, namely: (1) why
TIFA-GCL can enhance GCL effect and (2) alleviate the over-smoothing problem
in GNN training, (3) how to conduct graph-specific hard negative sampling and
(4) when weighted neighbor sampling promoting inductive graph training. Due to
the limit of space, we present the discussion of the last three research
questions in Appendix D.

###  5.1 TIFA-GCL Enhance Under-represented Nodes

To explore why our TIFA-GCL method can benefit SSNC more than uniform-GCL, we
display the comparison between TIFA-GCL with uniform-GCL at each TIG ranking
bin in Figure 4. We can find that TIFA-GCL outperforms uniform-GCL by a large
margin at nodes with small TIG values and achieves comparable performance at
nodes with large TIG values. This indicates that our TIFA-GCL can effectively
strengthen the GCL’s effect for nodes that are under-represented in graph
learning (small TIG value represents that node’s received annotated
information from topology is insufficient or confusing), thus achieving higher
performance than existing uniform-GCL methods.

Figure 4: The performance improvement gap across TIG ranking bins from the
largest to the lowest.

##  6 Related Work

The idea behind contrastive learning is to utilize self-supervision
information among contrastive pairs, which are constructed by randomly
perturbation. By regularizing the perturbed representations, e.g., pulling the
distance between positive pairs closer while pushing negative pairs apart, CL
learns high quality representations for both images Chen et al. (2020c); Sohn
et al. (2020); Berthelot et al. (2019) and texts Chen et al. (2020b); Qu et
al. (2021); Luo et al. (2020).

In graph field, Velickovic et al. (2019); Ren et al. (2019) learn node
representations via mutual information maximization, which can be treated as
the early applications of the idea of CL in graph. Recent GCL studies on SSNC
mainly focus on three topics: (1) Devising graph-specific CL frameworks by
combining GCL with different modules: such as pre-training Qiu et al. (2020),
graph generating target Wan et al. (2021), implicit contrastive method Kefato
and Girdzijauskas (2021), and light-weighted regularization Ma et al. (2021);
(2) Developing graph data augmentation methods, such as graph diffusion
Hassani and Khasahmadi (2020), random propagation Feng et al. (2020), subgraph
aggregation Wang and Liu (2021), and generating from different GNN encoders
Wan et al. (2021); and (3) Analyzing important questions in GCL, such as the
augmentation method You et al. (2020), GCL robustness Jovanovic et al. (2021),
sampling strategies Chen et al. (2021). However, all these existing GCL
methods ignore the imbalanced annotated information distribution and apply GCL
uniformly to the whole graph. Our TIFA-GCL can solve this issue by considering
the TIG of different nodes.

##  7 Conclusion and Future Work

In this work, we investigate contrastive learning in semi-supervised node
classification. We point out that current GCL methods lack consideration of
the uneven distribution of annotated information, which greatly affects the
graph learning performance. By analyzing the distributions of annotated
information GCL contribution, we find that the benefit brought by GCL in node
representation learning mainly comes from the nodes with less annotated
information. Motivated by our findings, we systematically devise the TIFA-GCL
framework. Extensive experiments in various scenarios demonstrate the
effectiveness and generalizability of our method.

## Acknowledgements

We appreciate all the thoughtful and insightful suggestions from the anonymous
reviews. This work was supported in part by a Tencent Research Grant and
National Natural Science Foundation of China (No. 62176002). Xu Sun is the
corresponding author of this paper.

## References

  * Bai et al. [2021] Song Bai, Feihu Zhang, and Philip HS Torr.  Hypergraph Convolution and Hypergraph Attention.  Pattern Recognit., 110:107637, 2021.
  * Berthelot et al. [2019] David Berthelot, Nicholas Carlini, Ekin D Cubuk, Alex Kurakin, Kihyuk Sohn, Han Zhang, and Colin Raffel.  Remixmatch: Semi-supervised Learning with Distribution Alignment and Augmentation Anchoring.  arXiv preprint: 1911.09785, 2019.
  * Bianchi et al. [2019] Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi.  Graph Neural Networks with Convolutional Arma Filters.  arXiv preprint: 1901.01343, 2019.
  * Buchnik and Cohen [2018] Eliav Buchnik and Edith Cohen.  Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity.  Proc. ACM Meas. Anal. Comput. Syst., 2(1):10:1–10:19, 2018.
  * Chen et al. [2020a] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun.  Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View.  In AAAI, 2020.
  * Chen et al. [2020b] Jiaao Chen, Zichao Yang, and Diyi Yang.  MixText: Linguistically-Informed Interpolation of Hidden Space for Semi-Supervised Text Classification.  In ACL, 2020.
  * Chen et al. [2020c] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton.  A Simple Framework for Contrastive Learning of Visual Representations.  In ICML, 2020.
  * Chen et al. [2021] Shiyi Chen, Ziao Wang, Xinni Zhang, Xiaofeng Zhang, and Dan Peng.  Probing Negative Sampling Strategies to Learn Graph Representations via Unsupervised Contrastive Learning.  arXiv preprint: 2104.06317, 2021.
  * Defferrard et al. [2016] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.  Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering.  In NeurIPS, 2016.
  * Feng et al. [2020] Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang.  Graph random neural networks for semi-supervised learning on graphs.  In NeurIPS, 2020.
  * Hamilton et al. [2017] William L. Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive Representation Learning on Large Graphs.  In NeurIPS, 2017.
  * Hassani and Khasahmadi [2020] Kaveh Hassani and Amir Hosein Khasahmadi.  Contrastive Multi-View Representation Learning on Graphs.  In ICML, 2020.
  * He et al. [2020] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum Contrast for Unsupervised Visual Representation Learning.  In CVPR, 2020.
  * Hu et al. [2020] 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 NeurIPS, 2020.
  * Jovanovic et al. [2021] Nikola Jovanovic, Zhao Meng, Lukas Faber, and Roger Wattenhofer.  Towards Robust Graph Contrastive Learning.  arXiv preprint: 2102.13085, 2021.
  * Kefato and Girdzijauskas [2021] Zekarias T. Kefato and Sarunas Girdzijauskas.  Self-supervised Graph Neural Networks without Explicit Negative Sampling.  arXiv preprint: 2103.14958, 2021.
  * Kingma and Ba [2015] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
  * Kipf and Welling [2017] Thomas N Kipf and Max Welling.  Semi-supervised Classification with Graph Convolutional Networks.  In ICLR, 2017.
  * Li et al. [2018] Qimai Li, Zhichao Han, and Xiao-Ming Wu.  Deeper Insights into Graph Convolutional Networks for Semi-supervised Learning.  In AAAI, 2018.
  * Luo et al. [2020] Fuli Luo, Pengcheng Yang, Shicheng Li, Xuancheng Ren, and Xu Sun.  CAPT: Contrastive Pre-Training for Learning Denoised Sequence Representations.  arXiv preprint: 2010.06351, 2020.
  * Ma et al. [2021] Kaili Ma, Haochen Yang, Han Yang, Tatiana Jin, Pengfei Chen, Yongqiang Chen, Barakeel Fanseu Kamhoua, and James Cheng.  Improving Graph Representation Learning by Contrastive Regularization.  arXiv preprint:2101.11525, 2021.
  * Morris et al. [2019] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.  Weisfeiler and Leman go Neural: Higher-order Graph Neural Networks.  In AAAI, 2019.
  * Nair and Hinton [2010] Vinod Nair and Geoffrey E Hinton.  Rectified Linear Units Improve Restricted Boltzmann Machines.  In ICML, 2010.
  * Qiu et al. [2020] Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang.  GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training.  In KDD, 2020.
  * Qu et al. [2021] Yanru Qu, Dinghan Shen, Yelong Shen, Sandra Sajeev, Weizhu Chen, and Jiawei Han.  CoDA: Contrast-enhanced and Diversity-promoting Data Augmentation for Natural Language Understanding.  In ICLR, 2021.
  * Ren et al. [2019] Yuxiang Ren, Bo Liu, Chao Huang, Peng Dai, Liefeng Bo, and Jiawei Zhang.  Heterogeneous Deep Graph Infomax.  arXiv preprint:1911.08538, 2019.
  * Robinson et al. [2021] Joshua David Robinson, Ching-Yao Chuang, Suvrit Sra, and Stefanie Jegelka.  Contrastive Learning with Hard Negative Samples.  In ICLR, 2021.
  * Schroff et al. [2015] Florian Schroff, Dmitry Kalenichenko, and James Philbin.  Facenet: A Unified Embedding for Face Recognition and Clustering.  In CVPR, 2015.
  * Sen et al. [2008] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad.  Collective Classification in Network Data.  AI magazine, 29(3):93–93, 2008.
  * Shchur et al. [2018] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann.  Pitfalls of Graph Neural Network Evaluation.  arXiv preprint: 1811.05868, 2018.
  * Sohn et al. [2020] Kihyuk Sohn, David Berthelot, Chun-Liang Li, Zizhao Zhang, Nicholas Carlini, Ekin D Cubuk, Alex Kurakin, Han Zhang, and Colin Raffel.  Fixmatch: Simplifying Semi-supervised Learning with Consistency and Confidence.  In NeurIPS, 2020.
  * Sun et al. [2019] Ke Sun, Piotr Koniusz, and Jeff Wang.  Fisher-Bures Adversary Graph Convolutional Networks.  In Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence, 2019.
  * Veličković et al. [2018] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph Attention Networks.  In ICLR, 2018.
  * Velickovic et al. [2019] Petar Velickovic, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm.  Deep Graph Infomax.  In ICLR, 2019.
  * Verma et al. [2018] Nitika Verma, Edmond Boyer, and Jakob Verbeek.  Feastnet: Feature-steered Graph Convolutions for 3d Shape Analysis.  In CVPR, 2018.
  * Verma et al. [2019] Vikas Verma, Meng Qu, Alex Lamb, Yoshua Bengio, Juho Kannala, and Jian Tang.  GraphMix: Regularized Training of Graph Neural Networks for Semi-Supervised Learning.  arXiv preprint: 1909.11715, 2019.
  * Wan et al. [2021] Sheng Wan, Shirui Pan, Jian Yang, and Chen Gong.  Contrastive and Generative Graph Convolutional Networks for Graph-based Semi-Supervised Learning.  In AAAI, 2021.
  * Wang and Leskovec [2020] Hongwei Wang and Jure Leskovec.  Unifying Graph Convolutional Neural Networks and Label Propagation.  arXiv preprint: 2002.06755, 2020.
  * Wang and Liu [2021] Chenguang Wang and Ziwen Liu.  Graph Representation Learning by Ensemble Aggregating Subgraphs via Mutual Information Maximization.  arXiv preprint: 2103.13125, 2021.
  * Wang et al. [2020] Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, Juncheng Liu, and Bryan Hooi.  NodeAug: Semi-Supervised Node Classification with Data Augmentation.  In KDD, 2020.
  * Xie et al. [2021] Qizhe Xie, Zihang Dai, Eduard H. Hovy, Thang Luong, and Quoc Le.  Unsupervised Data Augmentation for Consistency Training.  In NeurIPS, 2021.
  * Yang et al. [2016] Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov.  Revisiting Semi-supervised Learning with Graph Embeddings.  In ICML, 2016.
  * Yang et al. [2020] Zhen Yang, Ming Ding, Chang Zhou, Hongxia Yang, Jingren Zhou, and Jie Tang.  Understanding Negative Sampling in Graph Representation Learning.  In KDD, 2020.
  * You et al. [2020] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen.  Graph Contrastive Learning with Augmentations.  In NeurIPS, 2020.
  * Zeng et al. [2020] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna.  GraphSAINT: Graph Sampling Based Inductive Learning Method.  In ICLR, 2020.
  * Zhao and Akoglu [2019] Lingxiao Zhao and Leman Akoglu.  PairNorm: Tackling Oversmoothing in GNNs.  arXiv preprint: 1909.12223, 2019.
  * Zhu et al. [2020] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang.  Deep Graph Contrastive Representation Learning.  arXiv preprint: 2006.04131, 2020.
  * Zhu et al. [2021] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang.  Graph Contrastive Learning with Adaptive Augmentation.  In WWW, 2021.

##  Appendix A Supplement to the Probing of GCL

###  A.1 Adjust LP from the Node Feature view.

We propose that each unlabeled node owns its special preference for
information from different classes, which is influenced by the affinity of
node features. Therefore, we adopt the similarity between the unlabeled node
and the labeled node group’s prototype to adjust the original LP vector
$\bm{Z}_{i}$ from the node feature view:

$\displaystyle\bm{\mathcal{P}}_{c}$
$\displaystyle=\frac{1}{|\bm{{L}}_{c}|}\sum_{i\in\bm{{L}}_{c}}\bm{X}_{i},$
(15) $\displaystyle\bm{Z}_{i,c}^{\ast}$
$\displaystyle=\frac{1}{2}\bm{Z}_{i,c}\left(1+\frac{\bm{X}_{i}\bm{\mathcal{P}}_{c}^{T}}{\|\bm{X}_{i}\|\|\bm{\mathcal{P}}_{c}\|}\right),$
(16)

where $\bm{\mathcal{P}}_{c}$ is the prototype embedding of class $c$,
calculated by averaging the embedding of all the labeled nodes in class $c$
666We try different similarity metrics and find the cosine method works best.
. $\bm{Z}_{i,c}^{\ast}$ is applied in the analysis and experiment of this
work. Experiment results demonstrate that this modification from the node
feature view can further improve the final performance of our method.

###  A.2 Radial Decay Phenomenon in more Datasets

We observe the same radial decay phenomenon in CiteSeer and PubMed datasets in
Figure 5, which is in consistent with the conclusion in the GCL working
mechanism probing section.

###  A.3 The GCL Effect across TIG Ranking Bins

We show the GCL effect across TIG ranking bins in Figure 6. We can conclude
that the effect of GCL mainly comes from subgraphs with less annotated
information.

Figure 5:  The RADIAL DECAY phenomenon of SSNC in CiteSeer and PubMed
datasets, which is in consistent with the phenomenon in CORA dataset (Figure
1(a)). The white space in the lower right corner of the Subfigure (a) is
because we don’t plot nodes that have no topology information. CORA and
CiteSeer datasets have some isolated nodes whose LP vector is filled with
value $0$. PubMed dataset has no isolated node.  Figure 6: The GCL effect
across TIG ranking bins from the largest to the lowest (ranking 0%-100%). The
GCL results here are taken from our implementation with GCN as aggregator. The
shared model architectures between GCN and GCL are strictly aligned. We can
obviously find that: (1) GNN performs worse on nodes with fewer TIG values,
because the node’s received task information from labeled nodes is
insufficient or confuse; and (2) GCL, in contrast, mainly improves GNN’s
learning ability on nodes with fewer TIG values.

1:Graph $\mathcal{G}=(\mathcal{\bm{V}},\mathcal{\bm{E}})$ with adjacency
matrix $\bm{A}$; Sampling parameters: root nodes number $n$, random walk
length $h$, sharpening coefficient $t$, the global topology distance matrix
$\bm{D}^{g}$, error term $\varepsilon$.

2:$\mathcal{\bm{V}}_{root}\leftarrow n$ root nodes uniformly sampled from
$\mathcal{\bm{V}}$

3:$\mathcal{\bm{V}}_{s}\leftarrow\mathcal{\bm{V}}_{root}$

4:$\bm{P}(i,j)\leftarrow\frac{\bm{A}(i,j)}{\bm{D}^{g}(i,j)+\varepsilon}$
$\triangleright$ Make nodes with similar received annotated information more
likely to be sampled; mask non-neighbor pairs.

5:$\bm{P}((i,j)\in\mathcal{\bm{E}})=\frac{\mathrm{exp}(\bm{P}(i,j)\ast
t)}{\sum_{k\in\bm{A}(i,:)}\mathrm{exp}(\bm{P}(i,k)\ast t)}$ $\triangleright$
Sharpen sampling probability distribution with $t$.

6:for $v\in\mathcal{\bm{V}}_{root}$: do

7: $u\leftarrow v$

8: for $x=1$ to $h$ do

9: $u\leftarrow$ Node sampled from $u^{\prime}s$ neighbors by $\bm{P}(u,:)$

10: $\mathcal{\bm{V}}_{s}\leftarrow\mathcal{\bm{V}}_{s}\cup\\{u\\}$

11: end for

12:end for

13:$\mathcal{G}_{s}\leftarrow$ Node induced subgraph of $\mathcal{G}$ from
$\mathcal{V}_{s}$

14:$\mathcal{G}_{s}$

Algorithm 1 SAINT-TIFA: Global Topology Distance–Weighted Subgraph Sampling

1:Graph $\mathcal{G}=(\mathcal{\bm{V}},\mathcal{\bm{E}})$ with adjacency
matrix $\bm{A}$; Node embedding dim $h$, CL weight $\bm{w}$, sharpen
coefficient $t$, perturbation threshold $\sigma$, maximum edge adding/removing
number $n_{add},n_{rmv}$, feature mask rate $m$, probability decay hop range
$d_{h}$ and probability decay ratio $d_{r}$.

2:

3:function PROBABILITY_DECAY($\bm{P},\mathrm{i}$) $\triangleright$ Reduce the
perturbation probability of subgraphs around the nodes that have been
perturbed.

4: $\bm{P}[i]=0$

5: for $x\in$ node $i^{\prime}s$ neighbors within $d_{h}$ hops do

6: $\bm{P}[x]=\bm{P}[x]*d_{r}$

7: end for

8:
$\bm{P}[i]=\frac{\mathrm{exp}(\bm{P}[i])}{\sum_{k\in\mathcal{\bm{V}}}\mathrm{exp}(\bm{P}[i])}$

9: return $\bm{P}$

10:end function

11:

12:$\bm{X_{p}}\leftarrow\bm{X},\quad\bm{A_{p}}\leftarrow\bm{A}$

13:$\bm{P}[i]=\frac{\mathrm{exp}(w_{i}\ast
t)}{\sum_{k\in\mathcal{\bm{V}}}\mathrm{exp}(w_{k}\ast t)}$ $\triangleright$
Sharpen the selection probability distribution

14:$\mathrm{gap}\leftarrow 0$

15:while $\mathrm{gap}<\sigma$ do

16: $i\leftarrow$ sampled from $\mathcal{\bm{V}}$ according to probability
$\bm{P}$

17: $\mathcal{\bm{V}}_{add}\leftarrow n_{add}$ nodes uniformly sampled from
$i^{\prime}s$ nonadjacent nodes

18: for $x\in\mathcal{\bm{V}}_{add}$ do

19: $\bm{A_{p}}[x][\mathrm{i}]=\bm{A_{p}}[\mathrm{i}][x]=1$ $\triangleright$
Randomly add edges

20: end for

21: $\mathcal{\bm{V}}_{rmv}\leftarrow n_{rmv}$ nodes uniformly sampled from
$i^{\prime}s$ adjacent nodes

22: for $x\in\mathcal{\bm{V}}_{rmv}$ do

23: $\bm{A_{p}}[x][\mathrm{i}]=\bm{A_{p}}[\mathrm{i}][x]=0$ $\triangleright$
Randomly remove edges

24: end for

25: $\mathbf{mask_{idx}}\leftarrow(m\ast h)$ ids uniformly sampled from $1-h$

26: for $x\in\mathbf{mask_{idx}}$ do

27: $\bm{X_{p}}[x]=0$ $\triangleright$ Randomly mask features.

28: end for

29: $\bm{P}=$PROBABILITY_DECAY$(\bm{P},\mathrm{i})$

30:
$\mathrm{gap}=\sqrt{\sum_{i=1}^{|\mathcal{\bm{V}}|}\sum_{j=1}^{|\mathcal{\bm{V}}|}(\bm{A_{p}}[i][j]-\bm{A}[i][j])^{2}}$
$\triangleright$ Calculating the Frobenius norm

31:end while

32:

33:$\bm{X_{p}},\bm{A_{p}}$

Algorithm 2 TIFA-Graph Perturbation with Negative Feedback

##  Appendix B Detailed Algorithms in Methodology

###  B.1 TIFA-Graph Perturbation Algorithm

Data augmentation (perturbation) is an essential component in contrastive
learning. In existing studies, there are two general ideas to remedy this
issue: randomly/heuristically choosing part of graph nodes to disturb Zhu et
al. (2020, 2021) or augmenting each node in its parallel universe Wang et al.
(2020). However, neither of these two approaches take account of the
differences of nodes’ received task information from labeled nodes, which
determine the node’s requirements for supplementary information from CL.

Following existing studies Zhu et al. (2020); Wang et al. (2020); You et al.
(2020), three kinds of augmentation operations are taken: (1) Randomly adding
edges; (2) Randomly removing edges; and (3) Randomly masking node features. We
conduct sequential selections for nodes, and dynamically adjust the selecting
probability by reducing the probability of subgraphs around the augmented
node, which aims to remedy the excessive issue caused by the spreading of
graph perturbation. The algorithm stops once the graph disturbance reaches a
preset threshold. The details of TIFA-graph perturbation is shown in Algorithm
2.

###  B.2 TIFA-GCL for Inductive Graph Learning

Transductive GNN training methods Kipf and Welling (2017); Yang et al. (2016);
Veličković et al. (2018) take the full graph as input, which can hardly be
applied to scenarios where the graphs are too large to train in a full-batch
manner. Generally, there are two kinds of solutions to address this issue and
conduct inductive training: (1) Hamilton et al. (2017) propose the GraphSAGE
method to train GNN on the entire graph and sample the neighbor sets during
the training process, and (2) Zeng et al. (2020) instead propose the
GraphSAINT method to sample the subgraphs firstly and then train GNN on the
subgraphs, which has proven more effective. Moreover, GraphSAINT-Random Walk
(short as SAINT-RW) has proven especially effective in practice Zeng et al.
(2020).

Our TIFA-GCL method can be seamlessly applied to the inductive learning
scenario with the SAINT-RW subgraph sampling method. However, SAINT-RW
conducts sampling uniformly from all neighbor nodes, which overlooks the
difference in node affinity with different neighbors. Chen et al. (2020a) have
proved that the working mechanism of GNN mainly lies in the interaction and
smoothness of high-affinity node-pairs containing similar information; and in
Figure 2 from the paper body, we find that neighbors with similar topology
information distribution are more likely to share the same class label.
Therefore, we propose SAINT-TIFA, a weighted neighbor sampling strategy to
make nodes more likely to interact with high-affinity neighbors, thus boosting
inductive GNN training. Specifically, we employ the global topology distance
from Eq.12 as an indicator to adjust the sampling probability for different
neighbors.

The SAINT-TIFA subgraph sampling algorithm is shown in Algorithm 1. We adjust
the preference to high-affinity neighbours with the sharpening coefficient
$t$. The larger the value of $t$, the more likely the SAINT-TIFA algorithm
will walk to neighbors with similar annotated information distribution. The
SAINT-TIFA sampling method degenerates to the standard SAINT-RW method when
$t$ is zero.

##  Appendix C Detailed Experiment Settings for Reproducibility

###  C.1 Linux Server

We run all the experiments on a Linux server, some important information is
listed:

  * •

CPU: Intel(R) Xeon(R) Silver 4210 CPU @ 2.20GHz $\times$ 40

  * •

GPU: NVIDIA GeForce RTX2080TI-11GB $\times$ 8

  * •

RAM: 125GB

  * •

cuda: 10.1.243

  * •

cudann: 7.6.5.32-1+cuda10.1

###  C.2 Python Package

We implement all deep learning methods based on Python3.7. The versions of
some important packages are listed:

  * •

torch: 1.6.0+cu101

  * •

torch-geometric: 1.6.1

  * •

torch-cluster:1.5.7

  * •

torch-sparse: 0.6.7

  * •

ogb: 1.2.4

  * •

scikit-learn: 0.23.2

  * •

numpy:1.19.1

  * •

scipy:1.5.2

###  C.3 Hyper-parameters Selection for TIFA-GCL Framework

In this part, we introduce the selection range for the model-agnostic hyper-
parameters in TIFA-GCL training framework. All the hyper-parameters are tuned
on the validation set. Selection list with bold fonts indicates that model
usually perform best with these values. Otherwise, it means that the
parameters are sensitive to different graph datasets and GNN models.

  * •

Random walk teleport probability $\alpha$ in Eq.2:
$\\{0.05,0.1,\bm{0.15},0.2,0.25\\}$,

  * •

Weight of topology information clarity comparing to intensity $\lambda$ in
Eq.7:
$\\{0,0.05,\bm{0.1},0.15,0.2,0.5\\}$,

  * •

Weight of CL loss with negative pairs comparing to positive pairs $\mu_{1}$ in
Eq.11:
$\\{0,0.1,0.25,\bm{0.33},\bm{0.5},1\\}$,

  * •

Weight of CL loss with node pairs comparing to self-consistence loss $\mu_{2}$
in Eq.12:
$\\{0,0.05,0.1,0.15,0.2,0.25\\}$,

  * •

Minimum value of CL loss weight comparing to CE loss in Eq.13:
$\\{0.5,0.75,\bm{1},1.5,2,2.5,3,3.5\\}$,

  * •

Maximum value of CL loss weight comparing to CE loss in Eq.13:
$\\{1,1.5,\bm{2},2.5,3,3.5,4,4.5,5\\}$,

  * •

Weight of local topology distance in relative distance measuring comparing to
global topology distance $\lambda_{1}$:
$\\{0,0.25,\bm{0.5},0.75,1,1.25,1.5\\}$,

  * •

Weight of node embedding distance in relative distance measuring comparing to
global topology distance $\lambda_{2}$:
$\\{0,0.25,0.5,\bm{0.75},1,1.25,1.5\\}$.

###  C.4 Hyper-parameters Selection for GNN Aggregator

In this part, we introduce the selection range for the model-specific hyper-
parameters for GNN aggregators. For all comparable GNN encoders, we stack GNN
layers with $\mathrm{ReLU}$ Nair and Hinton (2010) activation function. We use
the Adam optimizer Kingma and Ba (2015) and early stopping strategy in
training.

  * •

Hidden Size:$\\{16,32,\bm{64},\bm{128},256\\}$ 64 for transductive learning
and 128 for inductive learning,

  * •

GNN Layer:$\\{\bm{2},\bm{3},4,5\\}$ 2 for transductive learning and 3 for
inductive learning,

  * •

Learning Rate:$\\{0.005,\bm{0.0075},0.01,0.0125\\}$,

  * •

Dropout Probability: $\\{0.2,0.3,0.4,\bm{0.5},0.6\\}$.

Besides, the maximum training epoch is set to $200$; training will last for at
least $30$ epochs; after that, training will early stop if there is no
improvement on the validation set for $20$ epochs. We adopt $L_{2}$
regularization with weight $0.005$. The learning rate begins to decay after
$30$ epochs with decay coefficient $0.95$.

###  C.5 More Information about Experiment Datasets

The statistical information of the used datasets in the experiments is shown
in Table 4.

For all the datasets except for OGB-Products, we use the standard transductive
semi-supervised node classification setting Yang et al. (2016), i.e., each
category has $20$ nodes for training and $30$ nodes for validation, and all
the rest nodes are used for testing. Following Shchur et al. (2018) and Sun et
al. (2019), we run 20 random dataset splittings for these five datasets to
relieve the random error caused by dataset splitting. Besides, we repeat the
experiment 5 times for each dataset splitting. For the inductive training
dataset OGB-Products, we use the official Hu et al. (2020) dataset splitting
and repeat the experiment 10 times. The backbone GNN aggregator among all
methods is GCN (unless otherwise stated). In each group of contrast
experiments, the model architectures shared between the baselines and proposed
methods are strictly aligned, to clearly show the pure effect brought by our
method.

Dataset | #Node | #Edge | #Labeled | #Class | Train
---|---|---|---|---|---
CORA | 2,708 | 5,429 | 140 | 7 | Trans.
CiteSeer | 3,327 | 4,732 | 120 | 6 | Trans.
PubMed | 19,717 | 44,338 | 60 | 3 | Trans.
Photo | 7,487 | 119,043 | 160 | 8 | Trans.
Comp. | 13,381 | 245,778 | 200 | 10 | Trans.
Products | 2,449,029 | 123,718,280 | 196,615 | 47 | Induc.

Table 4: Statistical information about datasets. Trans. indicates transductive
learning and Induc. indicates inductive learning. Comp. is the short for the
Computers dataset.

Layer |  Accuracy% ($\uparrow$) |  MADGap ($\uparrow$)
---|---|---
GCN | GCL | TIFA-GCL | GCN | GCL | TIFA-GCL
2 | 79.3$\pm$1.7 | 81.6$\pm$1.8 | 83.6$\pm$0.8 | 0.82$\pm$0.02 | 0.85$\pm$0.02 | 0.87$\pm$0.01
4 | 76.2$\pm$1.2 | 81.3$\pm$1.6 | 82.7$\pm$1.4 | 0.77$\pm$0.04 | 0.78$\pm$0.02 | 0.78$\pm$0.01
6 | 62.0$\pm$9.9 | 77.0$\pm$2.5 | 79.5$\pm$1.5 | 0.66$\pm$0.10 | 0.76$\pm$0.02 | 0.77$\pm$0.02
8 |  43.5$\pm$10.3 | 68.5$\pm$8.2 | 75.8$\pm$4.7 | 0.62$\pm$0.10 | 0.65$\pm$0.08 | 0.72$\pm$0.05

Table 5: Analysis of the over-smoothing phenomenon in deep GNNs. MADGap
measures the GNN over-smoothing degree. $\uparrow$ means the bigger the
better. We can find that TIFA-GCL can effectively relieve the over-smoothing
phenomenon and improve model performance for deep GNNs. Figure 7: Heatmap of
TIFA-GCL’s performance under different negative pair sampling settings.

##  Appendix D Supplement to Analysis

###  D.1 TIFA-GCL Effectively Alleviates GNN Over-smoothing Issue

Over-smoothing is a common issue in GNN Zhao and Akoglu (2019); Li et al.
(2018), especially for GNNs with multiple layers stacked. In Table 5, we
display MADGap Chen et al. (2020a); Feng et al. (2020), an indicator for GNN
over-smoothness, of CORA dataset trained by GCN models with various layers. We
find that TIFA-GCL can effectively relieve the over-smoothing problem, thus
promoting the GNN performance even for deep GNNs. We analyze the reason lies
in that, the interactions of graph nodes make nodes similar with each other
Chen et al. (2020a), while vanilla GNN training lacks the mechanism for
pulling representations of nodes apart. GCL can relieve this issue via self-
consistency or pair-wise regularization; therefore the contrastive pairs are
crucial in this process. TIFA-GCL sample contrastive pairs for each node
individually by measuring relative distance, thus it can sample the more
appropriate contrastive pairs and alleviate the over-smoothing phenomenon more
effectively than uniform-GCL.

###  D.2 Trade-off between Sampling Size and Difficulty of Negative
Contrastive Pair

Contrastive pair sampling has proven essential for the CL performance He et
al. (2020); Chen et al. (2020c). In Eq.17, we sample contrastive pairs by
measuring the relative distance from the anchor node to all the other nodes.
Empirical results show that the closest nodes work best as the positive
samples, and for the negative pair sampling, we further study the influence of
sampling size and difficulty in Figure 7. We observe that model can hardly be
trained well by too easy or too difficult negative pairs, while the semi-
difficult nodes serve best as negative samples. This phenomenon is in
consistent with CL studies Schroff et al. (2015); Robinson et al. (2021) in
scenes other than graph and proves the effectiveness of our relative distance
measuring (Eq.16). Besides, we notice that increasing the negative sampling
size can effectively improve CL performance, because more contrastive pairs
can provide more reliable target He et al. (2020). However, a large sampling
size will naturally reduce the difficulty of the selected pairs, telling that
there is a trade-off between sampling size and difficulty of contrastive
pairs.

###  D.3 When Weighted Neighbor Sampling Promotes Inductive Graph Training

We propose the SAINT-TIFA method to sample high-affinity neighbors instead of
the random sampling method Zeng et al. (2020). In this part, we further study
the influence of the preference to high-affinity neighbors. In Table 6, we
sharpen the distribution of sampling probability under different random walk
steps. We can find that, when we concentrate the sampling probability to the
high-affinity neighbors, the model performance can be effectively improved,
especially when the walking length is large. However, it is worth noticing
that when the sharpening coefficient is relatively large or the random walk
length is small, the model performance declines obviously. We speculate the
reason lies in that a GNN model needs to learn some negative examples for
training to avoid the trivial solution. We conclude from this experiment that,
when the walking length is small, dispersing the sampling probability
distribution is the optimal; while when the walking length increases, a larger
sharpening coefficient can be taken to improve the quality of sampled
subgraphs, thus promoting the inductive graph learning result.

$t$ | STD. | WL=2 | WL=3 | WL=4 | WL=5
---|---|---|---|---|---
0.00 | 0.000 | 81.6$\pm$0.8 | 82.1$\pm$0.3 | 80.4$\pm$0.9 | 80.4$\pm$0.9
0.25 | 0.010 | 81.2$\pm$1.6 |  82.5$\pm$0.5 | 81.2$\pm$1.2 | 80.2$\pm$2.4
0.50 | 0.022 | 79.6$\pm$1.4 | 81.4$\pm$1.2 | 81.9$\pm$1.3 | 80.8$\pm$3.0
1.00 | 0.032 | 79.9$\pm$1.9 | 80.7$\pm$1.6 | 80.7$\pm$1.4 | 80.9$\pm$2.1
2.00 | 0.040 | 79.3$\pm$2.7 | 79.3$\pm$0.9 | 79.4$\pm$1.2 | 79.7$\pm$2.1

Table 6: Analysis of the preference to high-affinity neighbors in SAINT-TIFA.
$t$ is the sharpening coefficient in Algorithm 1. STD. indicates the standard
deviation for the sampling probabilities. WL is the length of walking steps.


# Searching for Parity Violation in SDSS DR16 Lyman-$\alpha$ Forest Data

Prakruth Adari  Physics and Astronomy Department, Stony Brook University,
Stony Brook, NY 11794  Anže Slosar  Brookhaven National Laboratory, Upton NY
11973

###### Abstract

The four-point correlation function is the lowest order correlation function
for scalar fields that can be used to probe statistical parity invariance in
an isotropic universe. There are intriguing claims of detection of parity
violation in the 4-point function of BOSS galaxy clustering data. We apply the
same estimator to the public SDSS Data Release 16 Lyman-$\alpha$ forest data.
Lyman-$\alpha$ forest data probes a different redshift range and is sensitive
to a different density regime using a completely different technique. A
detection would therefore be a strong indication of new physics. We identify
accurate covariance matrix as a crucial impediment to performing this
measurement accurately, consistent with existing literature on galaxy 4-point
function. We discuss several approaches to estimating the covariance matrix,
several of which produce spurious detection. Using a robust, but very
suboptimal, covariance matrix derived from subsample bootstrapping, we find no
evidence for parity violation.

††preprint: APS/123-QED

##  I Introduction

Testing parity invariance of the large scale structure of the universe is one
of the foundational cosmological tests. If the large-scale structure of the
universe statistically violates parity, that would have a profound impact on
our understanding of fundamental physics. It would imply that either the
cosmological inflation contains parity-violating terms that generated parity
violation in the initial conditions or, perhaps even more far-fetched, that
gravitational evolution is parity violating, generating parity-violating
distribution of matter in the universe from what were parity invariant initial
conditions.

Using scalar fields, the lowest order parity violating correlator is a 4-point
function assuming an isotropic universe. Geometrically, the action of parity
transformation can be achieved using rotation in 3D for a line (2-pt) or a
triangle (3-pt), but not for a general tetrahedron which corresponds to a
4-point function. Recent searches for parity violations in galaxy clustering
have found a detection in distribution of BOSS galaxies by two groups, albeit
employing similar methods and the same data [1, 2]. When a similar search has
been repeated for the CMB, on both temperature and polarization data, no
signal has been found in either [3, 4]. Under certain scaling assumption, the
CMB result is much more constraining, but this statement hides considerable
model dependence. It is therefore imperative to understand the original of
this signal better and to search for it in other datasets.

In this paper, we repeat the same test on data from the Lyman-$\alpha$ forest
data from eBOSS data[5]. Lyman-$\alpha$ forests trace the cosmic structure at
different redshifts and with very different systematics compared to galaxy
clustering. In this paper, we set to measure this quantity using the eBOSS
Data Release 16 data [6]. We find no detection of parity violation, but we
also again identify the covariance matrix of the measurement as the most
difficult part of analysis, since the usual systematics present in the data do
not generate parity violation signal unless one is already present. As a by-
product, we have performed some of the first investigation of 3D polyspectra
for Lyman-$\alpha$ forests on observed data.

##  II Data & Method

The main observable in the Lyman-$\alpha$ forest is the transmitted flux
fluctuation (see [7] for a pedagogical introduction):

$\delta_{F}=\frac{F(\mathbf{x})}{\bar{F}(\mathbf{x})}-1,$ (1)

The value of $\delta_{F}$ traces the underlying neutral hydrogen fluctuations
in a very non-linear and mildly non-local manner. In absence of the large-
scale photo-ionizing fluctuations, $\delta_{F}$ traces the linear matter
fluctuations on the largest scales following linear bias models for the same
reasons as galaxies do. Most importantly, known physics cannot generate parity
violating signal in $\delta_{F}$ unless these is some already present in the
underlying fluctuations.

We use Sloan Digital Sky Survey’s DR16 Lyman-$\alpha$ spectroscopic data [8,
6, 5] as our input catalog. We rely on the public DR16
catalog111https://www.sdss4.org/dr16/spectro/lyman-alpha-forest/. In this
catalog, the quasars have already been continuum fitted and measurements were
converted into wavelength estimates ($\lambda$), flux fluctuations
($\delta_{F}$), and flux fluctuation inverse variance weights ($w$). The
wavelength is converted into redshift using $z=\lambda/\lambda_{\alpha}-1$,
where $\lambda_{\alpha}=1215.7\,\AA$ is the rest-frame wavelength of the
Lyman-$\alpha$ transition. Redshifts are in turn converted into comoving
radial distances using a fiducial cosmological model with parameters
$\Omega_{c}=0.27$, $\Omega_{b}=0.045$, $h=0.7$, $\sigma_{8}=0.8$ and
$n_{s}=0.96$. In total, we use 200,000 quasars and over $3.43\times 10^{7}$
data points along the lines of sight. For pipeline testing we use a set of
DR11 mock spectra [9] with similar number of quasars, total points along the
line of sights, and redshift range. The spectra are generated with the same
cosmological parameters listed above.

We perform very modest data cuts, removing the lowest-SNR data. In particular,
we require that $\lvert\delta_{F}\rvert<5$ and $w>0.1$ which leaves $3.38\cdot
10^{7}$ points, removing $2\%$ of the data which is quite noisy. This cut is
required by our approach at measuring the 4-point function as we describe
next.

To calculate the 4-point function, we employ a Landy-Szalay (LS) estimator as
implemented in the `ENCORE` package [10]. LS estimator requires a data and
random catalog, which encodes the survey window function. We generate them as
follows. At every point for which we have a measurement of $\delta_{F}$, there
is associated object in the LS catalogs with the same RA, DEC, and radial
distance. The associated weights for the signal catalog are given by
$w(1+\alpha\delta_{F})$ while for the random catalogs they are given by $w$.
The factor $\alpha$ simply rescales the resulting 4-point function signal by
$\alpha^{4}$. We have used $\alpha=0.1$ since `ENCORE` requires, for purely
technical reasons, that all weights are positive. We have tested that using a
different $\alpha$ and applying appropriate rescaling does not change the
result. We also apply a spatial cut in RA-DEC to split our data into 2
contiguous sets which can be seen in Fig. 1 separated by the galactic plane.
The South (“S”) set on the right contains 59,000 quasars with the remaining
151,000 quasars in the North (“N”) set on the left.

Figure 1: Distribution of quasars on sky. The left patch is labelled with “N”
and the right is labelled “S”.

What we measure is the spherically averaged 4-point function, $\zeta$, which
is parameterized by 3 distances $r_{1},r_{2},r_{3}$ and the 3 angular momenta
$l_{1},l_{2},l_{3}$. $\zeta$ can be expanded using a basis set
$\mathcal{P}_{l_{1},l_{2},l_{3}}$ which transforms as
$(-1)^{l_{1}+l_{2}+l_{3}}$ under the parity operation[11]. Furthermore, it can
be shown that due to the Wigner 3j terms and product of spherical harmonics
(which are indexed by $l_{1},l_{2},l_{3}$), $\mathcal{P}_{l_{1},l_{2},l_{3}}$
is real when $l_{1}+l_{2}+l_{3}$ is even and imaginary otherwise [11]. The
combination of these two properties along with the orthonormality of
$\mathcal{P}_{l_{1},l_{2},l_{3}}$ offers a convenient deconstruction of
$\zeta$ into a parity-even term, $\zeta_{+}$ which is a sum of real terms
only, and a parity-odd term, $\zeta_{-}$ which is a sum of imaginary terms
only[12]. Given a real density perturbation field we expect to measure
$\zeta_{-}=0$ and any deviation would be significant evidence of a parity
violation. We use 10 radial bins of size $\Delta r=15h^{-1}\textrm{Mpc}$ and
set $l_{i}\leq 4$ which gives a total of 56 radial bins and 23 angular bins.
Further details on the 4-point function can be found in [10, 13, 12, 11].

Following previous works on parity violation[3], we can calculate the number
of linear modes that would be present in our dataset from any primordial
signal[14]. We find there are $2\times 10^{5}$ linear modes in the data making
this comparable to the CMB results [3].

Figure 2: Histogram of $\chi^{2}$ scores when using the full covariance matrix
$\Sigma_{F}$. The left panel plots the distribution of scores using the
Estimate Set (ES) which are used to generate $\Sigma_{F}$ and the right is the
distribution for the Test Set (TS). We also include the $\chi^{2}$ from our
signal datavector on the right panel. Given that the TS comes from the same
overall set of realizations, this mismatch in distributions is indicative of
deeper problems with the covariance. Figure 3: Similar to Fig 2 but using
$\Sigma_{D}$, the covariance matrix generated by taking the diagonal of
$\Sigma_{F}$. To highlight the consistency between the Estimate Set, and Test
Set, the two distributions are both shown on the left panel. The right panel
plots the TS distribution along with $\chi^{2}$ from our signal datavector.
While we do satisfy our consistency check, we find that this signal can be
created on mock data as shown in Fig. 4. See Sec. II.2 for further details.
Figure 4: Similar to Fig 3 but using mock spectra. We create Mock Estimate Set
(MES) and Mock Test Set (MTS) of sizes 1900 and 100 respectively. The panel on
the left plots the distribution of $\chi^{2}$ scores of both the MES and MTS
to highlight that we are satisfying our consistency check while the right
panel plots the MTS scores and the mock signal $\chi^{2}$. Notably, there
should be no signal on mock data.

###  II.1 Signal and Covariance Matrix

We isolate the parity violating combinations of the 4-point function into a
vector $\mathbf{d}\in\mathbb{R}^{1288}$. In a parity conserving universe, the
expectation value for all those 4 point correlators is exactly zero, and
therefore the $\chi^{2}$ value defined as

$\chi^{2}=\mathbf{d}^{T}C^{-1}\mathbf{d}$ (2)

is expected to be $\chi^{2}$ distribution. A large value of $\chi^{2}$ would
be inconsistent with being drawn from this distribution and would signal
detection of parity violation.

The biggest problem is a robust estimation of the covariance matrix $C$. Since
the variable of interest is a 4-point function of the underlying field, the
estimator uncertainty, in general, depends on the 8-point function of the
underlying field. The 8 point function can in turn be written to have
contributions from four 2-point functions, followed by a product of two
disconnected 3-point functions and 2-point functions, etc. all the way to the
disconnected 8-point functions. This is in general extremely hard to compute,
but given that individual field measurements are noise dominated, it is
perhaps a valid assumption that the dominant contributions to uncertainty
comes from products of 2-point function, which we well denote as

$C^{d}_{ij}=\left<\delta_{F,i}\delta_{F,j}\right>.$ (3)

This covariance matrix $C^{d}$ can in turn be divided into three regimes: i)
diagonal part, i.e. variance of individual $\delta_{F}$ measurements is the
largest one and it receives contributions from both noise and 1-dimensional
correlations of the intrinsic signal along the line of sight; ii) the cross-
covariance of pairs of $\delta_{F}$ measurements from the same quasar, it
receives contributions from correlated noise due to continuum fitting and
intrinsic signal along the line of sight; iii) the cross-covariance of pairs
of $\delta_{F}$ measurements from pixels residing in nearby quasars receiving
contribution only from the intrinsic signal. Pairs of $\delta_{F}$
measurements from distant quasars are uncorrelated. When calculating the
2-point correlation function, it is usually a decent approximation to ignore
the contribution from iii), since it is the smallest.

###  II.2 Covariance Matrix from Quasar Shuffling

Based on this intuition, our first attempt to calculate covariance matrix was
to randomly shuffle quasar positions. We swapped the RA and DEC for all points
along a line of sight (LOS) with another LOS in order to maintain the
covariance terms from i and ii, and then the corresponding 4-point function
was calculated. This process was repeated 2000 times. 1900 were used to
estimate the covariance, $\Sigma_{F}$, and the remaining 100 were preserved as
a self-consistency check. The former is labelled the Estimate Set (ES) and the
latter as the Test Set (TS). The distribution of $\chi^{2}$ scores on the ES
is shown in the left panel of Fig. 2 and the TS is shown on the right. As seen
in the right panel, the distribution is massively misaligned with the expected
mean of 1288. We remedy this by taking only the diagonal terms in
$\Sigma_{F}$, $\Sigma_{D}$, which produces the $\chi^{2}$ distributions shown
in Fig. 3. As shown on the panel on the left, there is good agreement between
the ES and TS $\chi^{2}$ distributions. The mean and standard deviation for
each set and variation (see Appendix A) can be found in Table 1.

We see that in both cases, the real, unshuffled data is inconsistent with the
test data with a very large significance. This is a completely internally
derived covariance matrix that, especially in the diagonal case, seems to pass
our consistency test. However, when our entire process is repeated on a single
DR11 mock – shuffling RA&DEC, calculating $\xi$, estimating covariance, and
taking the diagonal term – we find a spurious signal from our mock which is
shown in Fig. 4. This implies that shuffling is a fundamentally flawed as it
is clearly destroying correlations that contribute significantly to the
measurement covariance matrix. We have attempted a few other approaches to
estimating the covariance matrix without success – for completeness we detail
them in then Appendix A.

Figure 5: Splitting the S patch into 12 subpatches each with 4882 quasars per
subpatch. The x-axis corresponds to a shifted RA to have a contiguous range.
Figure 6: Same as Fig 5 but with 32 subpatches each with 1831 quasars per
subpatch. Figure 7: Distribution of $\chi^{2}$ scores using the combined
diagonal bootstrapped covariance matrix. Left plot uses 12 subpatches while
right uses 32 subpatches. The red and black lines correspond to the $\chi^{2}$
score using the full data set or the mean of the subpatches correspondingly.

###  II.3 Covariance Matrix from Bootstrap Resampling

The spurious detection generated from quasar shuffling motivates our final
attempt which uses a bootstrap resampling method. Each patch (N or S) is split
into $N_{p}=$12 and $N_{p}=32$ subpatches as seen in Fig 5 and Fig 6 for the S
patch. We calculate the datavector in each subpatch independently and use the
standard bootstrap resampling algorithm to calculate the corresponding
covariance.

This means we repeatedly draw $N_{p}$ values from the subpatches _with
replacement_ and then calculate the mean. This is repeated 10,000 times and
that sample is used to estimate a covariance which we assume to be diagonal
due to the relatively small number of subpatches.

The diagonal bootstrapped covariances, $C^{d}_{N}$ and $C^{d}_{S}$, from the N
and S patch respectively, are then combined using

$C_{NS}^{d}=\left[\left(C_{N}^{d}\right)^{-1}+\left(C_{S}^{d}\right)^{-1}\right]^{-1}.$
(4)

Similarly the corresponding signal vector, $\mathbf{d}_{NS}$, from
$\mathbf{d}_{N}$ and $\mathbf{d}_{S}$ which come from the mean over all the
patches, via

$\mathbf{d}_{NS}=C_{NS}^{d}\left[\left(C_{N}^{d}\right)^{-1}\mathbf{d}_{N}+\left(C_{S}^{d}\right)^{-1}\mathbf{d}_{S}\right].$
(5)

Results for both values of $N_{p}$ are shown in Fig 7 where the data results
are consistent with no detection of parity-violating 4-point function.

##  III Conclusions

We have attempted to test for the presence of a parity-violating 4-point
function in the Lyman-$\alpha$ forest data. While the measurements can be
calculated using several existing and publicly available codes, determining a
reliable covariance matrix is very difficult.

We have attempted to determine the covariance matrix using quasar shuffling,
which preserves the dominant correlations present in a single quasar. The
diagonal version of this covariance matrix passes the basic sanity check in
that it produces a viable distribution of $\chi^{2}$ on a test shuffling set.
While it produces a strong detection, the same is obtained when the procedure
is repeated on a mock dataset. This implies that the basic premise of quasar-
shuffling approach, namely that the intra-quasars correlations dominate the
uncertainty is wrong.

We have not attempted to measure the covariance matrix using mocks alone for
two reasons. First, they correspond to an older, smaller catalog (DR11 rather
than DR16) and more importantly, are unlikely to capture the higher-order
correlations correctly since these were never designed to be used beyond
2-point function measurements. Recent work which suggests that the BOSS
detection can be attributed to an misestimated covariance [15] motivates our
conservative and suboptimal approach which produced a null result.

As shown in [16], the distribution of $\chi^{2}$ can be made to have the
correct mean by rescaling, but its spread around this mean for mock data
”measures” the deviation of the covariance matrix from the true one. Given our
number of points, the spread in $\chi^{2}$ should be around 50, but it is at
least an order of magnitude larger as shown in Figure 7. This means that it is
possible that even in this dataset, the signal could be present but we are
unable to ascertain its existence due to overly noisy covariance matrix.

In conclusion, we show that the test of parity violation based on 4-point
function of a scalar field is quite challenging in practice due to difficulty
in obtaining a reliable covariance matrix.

## Acknowledgements

We acknowledge useful discussions with Oliver Philcox. We acknowledge use of
the Core Cosmology Library [17], Matplotlib [18], Numpy [19], Scipy [20],
Healpy [21, 22], and the ColorBrewer.

##  Appendix A Covariance Matrix Estimations

We tried a number of methods to estimate the covariance matrix via quasar
shuffling by varying terms included. As a brief reminder, our data had been
binned into 23 angular bins and 56 radial bins leading 1288 points. We test
using five subsets of $\Sigma_{F}$:

  1. 1.

Full \- Use all radial and angular bins.

  2. 2.

Diagonal \- The simplest case wherein we remove any non-diagonal terms. Each
row has 1 non-zero value.

  3. 3.

Same Radial Bin \- All values from different radial bins are set to 0. Each
row has 23 non-zero values.

  4. 4.

Neighboring Radial Bin \- All values that are not in the same or neighboring
radial bin are set to 0. The smallest and largest radial bins have 46 non-zero
values while all middle radial bins have 69 non-zero values.

  5. 5.

Same Angular Bin \- All values from different angular bins are set to 0. Each
row has 56 non-zero values.

For all the methods, we generate 2000 realizations by shuffling quasars in the
S patch, use 1900 to estimate the covariance (ES) and 100 as a consistency
check (TS) as in the main text. We have checked that doing a completely random
shuffling and shuffling within redshift bins leads to similar $\chi^{2}$
distributions.

The mean and 1$\sigma$ standard deviation for the various methods on the ES
and the TS can be found in Table. 1. We found that the purely diagonal
covariance, $\Sigma_{D}$, led to the most consistent $\chi^{2}$ between the TS
and ES (Fig 3). As discussed in the main text, this consistency check is not
sufficient as the mocks produced a spurious signal as seen in Fig. 4.

| Full | Diagonal | Same Radial Bin | Neighboring Radial Bin | Same Angular Bin
---|---|---|---|---|---
Estimate Set | 1288 $\pm$ 43.3 | 1288 $\pm$ 72.1 | 1288 $\pm$ 70.9 | 1296 $\pm$ 68.4 | 1288 $\pm$ 68.4
Test Subset | 3659 $\pm$ 291.4 | 1296 $\pm$ 75.3 | 1309 $\pm$ 76.6 | 1351 $\pm$ 75.5 | 1332 $\pm$ 74.9
Table 1: Mean and standard deviation of $\chi^{2}$ distributions on simulation
data using a variety of covariance matrices.

## References

  * Philcox  _et al._ [2021a] O. H. E. Philcox, J. Hou, and Z. Slepian, A First Detection of the Connected 4-Point Correlation Function of Galaxies Using the BOSS CMASS Sample, (2021a), arXiv:2108.01670 [astro-ph.CO] .
  * Hou  _et al._ [2023] J. Hou, Z. Slepian, and R. N. Cahn, Measurement of parity-odd modes in the large-scale 4-point correlation function of Sloan Digital Sky Survey Baryon Oscillation Spectroscopic Survey twelfth data release CMASS and LOWZ galaxies, Mon. Not. Roy. Astron. Soc. 522, 5701 (2023), arXiv:2206.03625 [astro-ph.CO] .
  * Philcox [2023] O. H. Philcox, Do the cmb temperature fluctuations conserve parity?, arXiv preprint arXiv:2303.12106 (2023).
  * Philcox and Shiraishi [2024] O. H. E. Philcox and M. Shiraishi, Testing parity symmetry with the polarized cosmic microwave background, Phys. Rev. D 109, 083514 (2024).
  * Dawson  _et al._ [2016] K. S. Dawson, J.-P. Kneib, W. J. Percival, S. Alam, F. D. Albareti, S. F. Anderson, E. Armengaud, É. Aubourg, S. Bailey, J. E. Bautista, A. A. Berlind, M. A. Bershady, F. Beutler, D. Bizyaev, M. R. Blanton, M. Blomqvist, A. S. Bolton, J. Bovy, W. N. Brandt, J. Brinkmann, J. R. Brownstein, E. Burtin, N. G. Busca, Z. Cai, C.-H. Chuang, N. Clerc, J. Comparat, F. Cope, R. A. C. Croft, I. Cruz-Gonzalez, L. N. da Costa, M.-C. Cousinou, J. Darling, A. de la Macorra, S. de la Torre, T. Delubac, H. du Mas des Bourboux, T. Dwelly, A. Ealet, D. J. Eisenstein, M. Eracleous, S. Escoffier, X. Fan, A. Finoguenov, A. Font-Ribera, P. Frinchaboy, P. Gaulme, A. Georgakakis, P. Green, H. Guo, J. Guy, S. Ho, D. Holder, J. Huehnerhoff, T. Hutchinson, Y. Jing, E. Jullo, V. Kamble, K. Kinemuchi, D. Kirkby, F.-S. Kitaura, M. A. Klaene, R. R. Laher, D. Lang, P. Laurent, J.-M. Le Goff, C. Li, Y. Liang, M. Lima, Q. Lin, W. Lin, Y.-T. Lin, D. C. Long, B. Lundgren, N. MacDonald, M. A. Geimba Maia, E. Malanushenko, V. Malanushenko, V. Mariappan, C. K. McBride, I. D. McGreer, B. Ménard, A. Merloni, A. Meza, A. D. Montero-Dorta, D. Muna, A. D. Myers, K. Nandra, T. Naugle, J. A. Newman, P. Noterdaeme, P. Nugent, R. Ogando, M. D. Olmstead, A. Oravetz, D. J. Oravetz, N. Padmanabhan, N. Palanque-Delabrouille, K. Pan, J. K. Parejko, I. Pâris, J. A. Peacock, P. Petitjean, M. M. Pieri, A. Pisani, F. Prada, A. Prakash, A. Raichoor, B. Reid, J. Rich, J. Ridl, S. Rodriguez-Torres, A. Carnero Rosell, A. J. Ross, G. Rossi, J. Ruan, M. Salvato, C. Sayres, D. P. Schneider, D. J. Schlegel, U. Seljak, H.-J. Seo, B. Sesar, S. Shandera, Y. Shu, A. Slosar, F. Sobreira, A. Streblyanska, N. Suzuki, D. Taylor, C. Tao, J. L. Tinker, R. Tojeiro, M. Vargas-Magaña, Y. Wang, B. A. Weaver, D. H. Weinberg, M. White, W. M. Wood-Vasey, C. Yeche, Z. Zhai, C. Zhao, G.-b. Zhao, Z. Zheng, G. Ben Zhu, and H. Zou, The SDSS-IV Extended Baryon Oscillation Spectroscopic Survey: Overview and Early Data, The Astronomical Journal 151, 44 (2016), arXiv:1508.04473 .
  * Ahumada  _et al._ [2020] R. Ahumada, C. Allende Prieto, A. Almeida, F. Anders, S. F. Anderson, B. H. Andrews, B. Anguiano, R. Arcodia, E. Armengaud, M. Aubert, S. Avila, V. Avila-Reese, C. Badenes, C. Balland, K. Barger, J. K. Barrera-Ballesteros, S. Basu, J. Bautista, R. L. Beaton, T. C. Beers, B. I. T. Benavides, C. F. Bender, M. Bernardi, M. Bershady, F. Beutler, C. M. Bidin, J. Bird, D. Bizyaev, G. A. Blanc, M. R. Blanton, M. Boquien, J. Borissova, J. Bovy, W. N. Brandt, J. Brinkmann, J. R. Brownstein, K. Bundy, M. Bureau, A. Burgasser, E. Burtin, M. Cano-Díaz, R. Capasso, M. Cappellari, R. Carrera, S. Chabanier, W. Chaplin, M. Chapman, B. Cherinka, C. Chiappini, P. Doohyun Choi, S. D. Chojnowski, H. Chung, N. Clerc, D. Coffey, J. M. Comerford, J. Comparat, L. da Costa, M.-C. Cousinou, K. Covey, J. D. Crane, K. Cunha, G. d. S. Ilha, Y. S. Dai, S. B. Damsted, J. Darling, J. Davidson, James W., R. Davies, K. Dawson, N. De, A. de la Macorra, N. De Lee, A. B. d. A. Queiroz, A. Deconto Machado, S. de la Torre, F. Dell’Agli, H. du Mas des Bourboux, A. M. Diamond-Stanic, S. Dillon, J. Donor, N. Drory, C. Duckworth, T. Dwelly, G. Ebelke, S. Eftekharzadeh, A. Davis Eigenbrot, Y. P. Elsworth, M. Eracleous, G. Erfanianfar, S. Escoffier, X. Fan, E. Farr, J. G. Fernández-Trincado, D. Feuillet, A. Finoguenov, P. Fofie, A. Fraser-McKelvie, P. M. Frinchaboy, S. Fromenteau, H. Fu, L. Galbany, R. A. Garcia, D. A. García-Hernández, L. A. Garma Oehmichen, J. Ge, M. A. Geimba Maia, D. Geisler, J. Gelfand, J. Goddy, V. Gonzalez-Perez, K. Grabowski, P. Green, C. J. Grier, H. Guo, J. Guy, P. Harding, S. Hasselquist, A. J. Hawken, C. R. Hayes, F. Hearty, S. Hekker, D. W. Hogg, J. A. Holtzman, D. Horta, J. Hou, B.-C. Hsieh, D. Huber, J. A. S. Hunt, J. Ider Chitham, J. Imig, M. Jaber, C. E. Jimenez Angel, J. A. Johnson, A. M. Jones, H. Jönsson, E. Jullo, Y. Kim, K. Kinemuchi, I. Kirkpatrick, Charles C., G. W. Kite, M. Klaene, J.-P. Kneib, J. A. Kollmeier, H. Kong, M. Kounkel, D. Krishnarao, I. Lacerna, T.-W. Lan, R. R. Lane, D. R. Law, J.-M. Le Goff, H. W. Leung, H. Lewis, C. Li, J. Lian, L. Lin, D. Long, P. Longa-Peña, B. Lundgren, B. W. Lyke, J. T. Mackereth, C. L. MacLeod, S. R. Majewski, A. Manchado, C. Maraston, P. Martini, T. Masseron, K. L. Masters, S. Mathur, R. M. McDermid, A. Merloni, M. Merrifield, S. Mészáros, A. Miglio, D. Minniti, R. Minsley, T. Miyaji, F. G. Mohammad, B. Mosser, E.-M. Mueller, D. Muna, A. Muñoz-Gutiérrez, A. D. Myers, S. Nadathur, P. Nair, K. Nandra, J. Correa do Nascimento, R. J. Nevin, J. A. Newman, D. L. Nidever, C. Nitschelm, P. Noterdaeme, J. E. O’Connell, M. D. Olmstead, D. Oravetz, A. Oravetz, Y. Osorio, Z. J. Pace, N. Padilla, N. Palanque-Delabrouille, P. A. Palicio, H.-A. Pan, K. Pan, J. Parker, R. Paviot, S. Peirani, K. P. Ramŕez, S. Penny, W. J. Percival, I. Perez-Fournon, I. Pérez-Ràfols, P. Petitjean, M. M. Pieri, M. Pinsonneault, V. J. Poovelil, J. T. Povick, A. Prakash, A. M. Price-Whelan, M. J. Raddick, A. Raichoor, A. Ray, S. B. Rembold, M. Rezaie, R. A. Riffel, R. Riffel, H.-W. Rix, A. C. Robin, A. Roman-Lopes, C. Román-Zúñiga, B. Rose, A. J. Ross, G. Rossi, K. Rowlands, K. H. R. Rubin, M. Salvato, A. G. Sánchez, L. Sánchez-Menguiano, J. R. Sánchez-Gallego, C. Sayres, A. Schaefer, R. P. Schiavon, J. S. Schimoia, E. Schlafly, D. Schlegel, D. P. Schneider, M. Schultheis, A. Schwope, H.-J. Seo, A. Serenelli, A. Shafieloo, S. J. Shamsi, Z. Shao, S. Shen, M. Shetrone, R. Shirley, V. Silva Aguirre, J. D. Simon, M. F. Skrutskie, A. Slosar, R. Smethurst, J. Sobeck, B. C. Sodi, D. Souto, D. V. Stark, K. G. Stassun, M. Steinmetz, D. Stello, J. Stermer, T. Storchi-Bergmann, A. Streblyanska, G. S. Stringfellow, A. Stutz, G. Suárez, J. Sun, M. Taghizadeh-Popp, M. S. Talbot, J. Tayar, A. R. Thakar, R. Theriault, D. Thomas, Z. C. Thomas, J. Tinker, R. Tojeiro, H. H. Toledo, C. A. Tremonti, N. W. Troup, S. Tuttle, E. Unda-Sanzana, M. Valentini, J. Vargas-González, M. Vargas-Magaña, J. A. Vázquez-Mata, M. Vivek, D. Wake, Y. Wang, B. A. Weaver, A.-M. Weijmans, V. Wild, J. C. Wilson, R. F. Wilson, N. Wolthuis, W. M. Wood-Vasey, R. Yan, M. Yang, C. Yèche, O. Zamora, P. Zarrouk, G. Zasowski, K. Zhang, C. Zhao, G. Zhao, Z. Zheng, Z. Zheng, G. Zhu, and H. Zou, The 16th Data Release of the Sloan Digital Sky Surveys: First Release from the APOGEE-2 Southern Survey and Full Release of eBOSS Spectra, The Astrophysical Journal Supplement Series 249, 3 (2020), arXiv:1912.02905 [astro-ph.GA] .
  * Slosar  _et al._ [2011] A. Slosar, A. Font-Ribera, M. M. Pieri, J. Rich, J.-M. L. Goff, É. Aubourg, J. Brinkmann, N. Busca, B. Carithers, R. Charlassier, M. Cortês, R. Croft, K. S. Dawson, D. Eisenstein, J.-C. Hamilton, S. Ho, K.-G. Lee, R. Lupton, P. McDonald, B. Medolin, D. Muna, J. Miralda-Escudé, A. D. Myers, R. C. Nichol, N. Palanque-Delabrouille, I. Pâris, P. Petitjean, Y. Piškur, E. Rollinde, N. P. Ross, D. J. Schlegel, D. P. Schneider, E. Sheldon, B. A. Weaver, D. H. Weinberg, C. Yeche, and D. G. York, The lyman-$\alpha$ forest in three dimensions: measurements of large scale flux correlations from BOSS 1st-year data, Journal of Cosmology and Astroparticle Physics 2011 (09), 001.
  * Blanton  _et al._ [2017] M. R. Blanton, M. A. Bershady, B. Abolfathi, F. D. Albareti, C. Allende Prieto, A. Almeida, J. Alonso-García, F. Anders, S. F. Anderson, B. Andrews, E. Aquino-Ortíz, A. Aragón-Salamanca, M. Argudo-Fernández, E. Armengaud, E. Aubourg, V. Avila-Reese, C. Badenes, S. Bailey, K. A. Barger, J. Barrera-Ballesteros, C. Bartosz, D. Bates, F. Baumgarten, J. Bautista, R. Beaton, T. C. Beers, F. Belfiore, C. F. Bender, A. A. Berlind, M. Bernardi, F. Beutler, J. C. Bird, D. Bizyaev, G. A. Blanc, M. Blomqvist, A. S. Bolton, M. Boquien, J. Borissova, R. van den Bosch, J. Bovy, W. N. Brandt, J. Brinkmann, J. R. Brownstein, K. Bundy, A. J. Burgasser, E. Burtin, N. G. Busca, M. Cappellari, M. L. Delgado Carigi, J. K. Carlberg, A. Carnero Rosell, R. Carrera, N. J. Chanover, B. Cherinka, E. Cheung, Y. Gómez Maqueo Chew, C. Chiappini, P. D. Choi, D. Chojnowski, C.-H. Chuang, H. Chung, R. F. Cirolini, N. Clerc, R. E. Cohen, J. Comparat, L. da Costa, M.-C. Cousinou, K. Covey, J. D. Crane, R. A. C. Croft, I. Cruz-Gonzalez, D. Garrido Cuadra, K. Cunha, G. J. Damke, J. Darling, R. Davies, K. Dawson, A. de la Macorra, F. Dell’Agli, N. De Lee, T. Delubac, F. Di Mille, A. Diamond-Stanic, M. Cano-Díaz, J. Donor, J. J. Downes, N. Drory, H. du Mas des Bourboux, C. J. Duckworth, T. Dwelly, J. Dyer, G. Ebelke, A. D. Eigenbrot, D. J. Eisenstein, E. Emsellem, M. Eracleous, S. Escoffier, M. L. Evans, X. Fan, E. Fernández-Alvar, J. G. Fernandez-Trincado, D. K. Feuillet, A. Finoguenov, S. W. Fleming, A. Font-Ribera, A. Fredrickson, G. Freischlad, P. M. Frinchaboy, C. E. Fuentes, L. Galbany, R. Garcia-Dias, D. A. García-Hernández, P. Gaulme, D. Geisler, J. D. Gelfand, H. Gil-Marín, B. A. Gillespie, D. Goddard, V. Gonzalez-Perez, K. Grabowski, P. J. Green, C. J. Grier, J. E. Gunn, H. Guo, J. Guy, A. Hagen, C. Hahn, M. Hall, P. Harding, S. Hasselquist, S. L. Hawley, F. Hearty, J. I. Gonzalez Hernández, S. Ho, D. W. Hogg, K. Holley-Bockelmann, J. A. Holtzman, P. H. Holzer, J. Huehnerhoff, T. A. Hutchinson, H. S. Hwang, H. J. Ibarra-Medel, G. da Silva Ilha, I. I. Ivans, K. Ivory, K. Jackson, T. W. Jensen, J. A. Johnson, A. Jones, H. Jönsson, E. Jullo, V. Kamble, K. Kinemuchi, D. Kirkby, F.-S. Kitaura, M. Klaene, G. R. Knapp, J.-P. Kneib, J. A. Kollmeier, I. Lacerna, R. R. Lane, D. Lang, D. R. Law, D. Lazarz, Y. Lee, J.-M. Le Goff, F.-H. Liang, C. Li, H. Li, J. Lian, M. Lima, L. Lin, Y.-T. Lin, S. Bertran de Lis, C. Liu, M. A. C. de Icaza Lizaola, D. Long, S. Lucatello, B. Lundgren, N. K. MacDonald, A. Deconto Machado, C. L. MacLeod, S. Mahadevan, M. A. Geimba Maia, R. Maiolino, S. R. Majewski, E. Malanushenko, V. Malanushenko, A. Manchado, S. Mao, C. Maraston, R. Marques-Chaves, T. Masseron, K. L. Masters, C. K. McBride, R. M. McDermid, B. McGrath, I. D. McGreer, N. Medina Peña, M. Melendez, A. Merloni, M. R. Merrifield, S. Meszaros, A. Meza, I. Minchev, D. Minniti, T. Miyaji, S. More, J. Mulchaey, F. Müller-Sánchez, D. Muna, R. R. Munoz, A. D. Myers, P. Nair, K. Nandra, J. Correa do Nascimento, A. Negrete, M. Ness, J. A. Newman, R. C. Nichol, D. L. Nidever, C. Nitschelm, P. Ntelis, J. E. O’Connell, R. J. Oelkers, A. Oravetz, D. Oravetz, Z. Pace, N. Padilla, N. Palanque-Delabrouille, P. Alonso Palicio, K. Pan, J. K. Parejko, T. Parikh, I. Pâris, C. Park, A. Y. Patten, S. Peirani, M. Pellejero-Ibanez, S. Penny, W. J. Percival, I. Perez-Fournon, P. Petitjean, M. M. Pieri, M. Pinsonneault, A. Pisani, R. Poleski, F. Prada, A. Prakash, A. B. d. A. Queiroz, M. J. Raddick, A. Raichoor, S. Barboza Rembold, H. Richstein, R. A. Riffel, R. Riffel, H.-W. Rix, A. C. Robin, C. M. Rockosi, S. Rodríguez-Torres, A. Roman-Lopes, C. Román-Zúñiga, M. Rosado, A. J. Ross, G. Rossi, J. Ruan, R. Ruggeri, E. S. Rykoff, S. Salazar-Albornoz, M. Salvato, A. G. Sánchez, D. S. Aguado, J. R. Sánchez-Gallego, F. A. Santana, B. X. Santiago, C. Sayres, R. P. Schiavon, J. da Silva Schimoia, E. F. Schlafly, D. J. Schlegel, D. P. Schneider, M. Schultheis, W. J. Schuster, A. Schwope, H.-J. Seo, Z. Shao, S. Shen, M. Shetrone, M. Shull, J. D. Simon, D. Skinner, M. F. Skrutskie, A. Slosar, V. V. Smith, J. S. Sobeck, F. Sobreira, G. Somers, D. Souto, D. V. Stark, K. Stassun, F. Stauffer, M. Steinmetz, T. Storchi-Bergmann, A. Streblyanska, G. S. Stringfellow, G. Suárez, J. Sun, N. Suzuki, L. Szigeti, M. Taghizadeh-Popp, B. Tang, C. Tao, J. Tayar, M. Tembe, J. Teske, A. R. Thakar, D. Thomas, B. A. Thompson, J. L. Tinker, P. Tissera, R. Tojeiro, H. Hernandez Toledo, S. de la Torre, C. Tremonti, N. W. Troup, O. Valenzuela, I. Martinez Valpuesta, J. Vargas-González, M. Vargas-Magaña, J. A. Vazquez, S. Villanova, M. Vivek, N. Vogt, D. Wake, R. Walterbos, Y. Wang, B. A. Weaver, A.-M. Weijmans, D. H. Weinberg, K. B. Westfall, D. G. Whelan, V. Wild, J. Wilson, W. M. Wood-Vasey, D. Wylezalek, T. Xiao, R. Yan, M. Yang, J. E. Ybarra, C. Yèche, N. Zakamska, O. Zamora, P. Zarrouk, G. Zasowski, K. Zhang, G.-B. Zhao, Z. Zheng, Z. Zheng, X. Zhou, Z.-M. Zhou, G. B. Zhu, M. Zoccali, and H. Zou, Sloan Digital Sky Survey IV: Mapping the Milky Way, Nearby Galaxies, and the Distant Universe, The Astronomical Journal 154, 28 (2017), arXiv:1703.00052 [astro-ph.GA] .
  * Bautista  _et al._ [2015] J. E. Bautista, S. Bailey, A. Font-Ribera, M. M. Pieri, N. G. Busca, J. Miralda-Escudé, N. Palanque-Delabrouille, J. Rich, K. Dawson, Y. Feng, J. Ge, S. G. A. Gontcho, S. Ho, J. M. Le Goff, P. Noterdaeme, I. Pâris, G. Rossi, and D. Schlegel, Mock Quasar-Lyman-$\alpha$ forest data-sets for the SDSS-III Baryon Oscillation Spectroscopic Survey, J. Cosmology Astropart. Phys 2015, 060 (2015), arXiv:1412.0658 [astro-ph.CO] .
  * Philcox  _et al._ [2021b] O. H. E. Philcox, Z. Slepian, J. Hou, C. Warner, R. N. Cahn, and D. J. Eisenstein, encore: an O (Ng2) estimator for galaxy N-point correlation functions, Mon. Not. Roy. Astron. Soc. 509, 2457 (2021b), arXiv:2105.08722 [astro-ph.IM] .
  * Cahn  _et al._ [2023] R. N. Cahn, Z. Slepian, and J. Hou, Test for Cosmological Parity Violation Using the 3D Distribution of Galaxies, Phys. Rev. Lett. 130, 201002 (2023), arXiv:2110.12004 [astro-ph.CO] .
  * Philcox [2022] O. H. E. Philcox, Probing parity violation with the four-point correlation function of boss galaxies, Phys. Rev. D 106, 063501 (2022).
  * Philcox and Slepian [2022] O. H. E. Philcox and Z. Slepian, Efficient computation of N-point correlation functions in D dimensions, Proc. Nat. Acad. Sci. 119, e2111366119 (2022), arXiv:2106.10278 [astro-ph.IM] .
  * Sailer  _et al._ [2021] N. Sailer, E. Castorina, S. Ferraro, and M. White, Cosmology at high redshift - a probe of fundamental physics, J. Cosmology Astropart. Phys 2021, 049 (2021), arXiv:2106.09713 [astro-ph.CO] .
  * Philcox and Ereza [2024] O. H. E. Philcox and J. Ereza, Could sample variance be responsible for the parity-violating signal seen in the boss galaxy survey? (2024), arXiv:2401.09523 [astro-ph.CO] .
  * Fumagalli  _et al._ [2022] A. Fumagalli, M. Biagetti, A. Saro, E. Sefusatti, A. Slosar, P. Monaco, and A. Veropalumbo, Fitting covariance matrix models to simulations, J. Cosmology Astropart. Phys 2022, 022 (2022), arXiv:2206.05191 [astro-ph.CO] .
  * Chisari  _et al._ [2019] N. E. Chisari, D. Alonso, E. Krause, C. D. Leonard, P. Bull, J. Neveu, A. Villarreal, S. Singh, T. McClintock, J. Ellison, Z. Du, J. Zuntz, A. Mead, S. Joudaki, C. S. Lorenz, T. Tröster, J. Sanchez, F. Lanusse, M. Ishak, R. Hlozek, J. Blazek, J.-E. Campagne, H. Almoubayyed, T. Eifler, M. Kirby, D. Kirkby, S. Plaszczynski, A. Slosar, M. Vrastil, and E. L. W. and, Core cosmology library: Precision cosmological predictions for LSST, The Astrophysical Journal Supplement Series 242, 2 (2019).
  * Hunter [2007] J. D. Hunter, Matplotlib: A 2d graphics environment, Computing in Science & Engineering 9, 90 (2007).
  * Harris  _et al._ [2020] C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, J. Taylor, S. Berg, N. J. Smith, R. Kern, M. Picus, S. Hoyer, M. H. van Kerkwijk, M. Brett, A. Haldane, J. F. del Río, M. Wiebe, P. Peterson, P. Gérard-Marchant, K. Sheppard, T. Reddy, W. Weckesser, H. Abbasi, C. Gohlke, and T. E. Oliphant, Array programming with NumPy, Nature 585, 357 (2020).
  * Virtanen  _et al._ [2020] P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, İ. Polat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen, E. A. Quintero, C. R. Harris, A. M. Archibald, A. H. Ribeiro, F. Pedregosa, P. van Mulbregt, and SciPy 1.0 Contributors, SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python, Nature Methods 17, 261 (2020).
  * Zonca  _et al._ [2019] A. Zonca, L. Singer, D. Lenz, M. Reinecke, C. Rosset, E. Hivon, and K. Gorski, healpy: equal area pixelization and spherical harmonics transforms for data on the sphere in python, Journal of Open Source Software 4, 1298 (2019).
  * Górski  _et al._ [2005] K. M. Górski, E. Hivon, A. J. Banday, B. D. Wandelt, F. K. Hansen, M. Reinecke, and M. Bartelmann, HEALPix: A Framework for High-Resolution Discretization and Fast Analysis of Data Distributed on the Sphere, ApJ 622, 759 (2005), arXiv:astro-ph/0409513 .