# Edge-featured Graph Neural Architecture Search

Shaofei Cai1,2, Liang Li1, Xinzhe Han1,2, Zheng-Jun Zha3, Qingming Huang1,2,4
1Key Lab of Intell. Info. Process., Inst. of Comput. Tech., CAS, Beijing,
China
2University of Chinese Academy of Sciences, Beijing, China
3University of Science and Technology of China, China, 4Peng Cheng Laboratory,
Shenzhen, China
shaofei.cai@vipl.ict.ac.cn,liang.li<EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>Corresponding author.

###### Abstract

Graph neural networks (GNNs) have been successfully applied to learning
representation on graphs in many relational tasks. Recently, researchers study
neural architecture search (NAS) to reduce the dependence of human expertise
and explore better GNN architectures, but they over-emphasize entity features
and ignore latent relation information concealed in the edges. To solve this
problem, we incorporate edge features into graph search space and propose
Edge-featured Graph Neural Architecture Search (EGNAS) to find the optimal GNN
architecture. Specifically, we design rich entity and edge updating operations
to learn high-order representations, which convey more generic message passing
mechanisms. Moreover, the architecture topology in our search space allows to
explore complex feature dependence of both entities and edges, which can be
efficiently optimized by differentiable search strategy. Experiments at three
graph tasks on six datasets show EGNAS can search better GNNs with higher
performance than current state-of-the-art human-designed and searched-based
GNNs.111Codes have been provided in supplementary materials, and will be
released via GitHub.

##  1 Introduction

Architecture design is a critical component of successful deep learning.
Lately, the neural architecture search (NAS) baker2016designing ; liu2018darts
; pham2018efficient ; zhang2021automated ; zoph2016neural has been extensively
studied to explore the optimal network architectures and lessen the manual
intervention. Most NAS works baker2016designing ; liu2018darts ;
pham2018efficient ; zoph2016neural focus on searching architectures about CNN
and RNN. Recently, graph neural networks (GNNs) have become standard toolkits
for analyzing complex graph-structure data, facilitating many relational tasks
such as chemical molecular property prediction, social network analysis and
recommendation. However, only a few efforts cai2021rethinking ;
zhang2021automated conceive NAS in graph machine learning domain. In this
paper, we study edge-featured graph neural architecture search to improve
GNN’s reasoning capability.

The core of GNNs is the message passing mechanism, which learns graph
representation by propagating feature information between neighboring
entities. This helps capture the semantic context implied in the graph. Unlike
image and sequence data, which have a grid structure, graph data lies in a
non-Euclidean space bronstein2017geometric , leading to unique architectures
and designs for graph machine learning. Typical search space of CNN/RNN NAS
focuses on improving the representation learning capability by combining
convolution, pooling and activation operations. Differently, graph search
space aims to explore effective message passing mechanisms, which is the key
challenge to solve graph neural architecture search problem.

Currently graph search spaces can be divided into two categories: macro- and
micro-space. Macro search space gao2020graph ; jiang2020graph is constructed
using popular GNNs (_e.g._ GIN xu2018powerful , GAT velivckovic2017graph ) as
atom operations, which is actually a kind of GNN ensemble and represents
limited message passing models. Micro search space consists of fine-grained
atomic operations such as neighbor aggregation, feature filtering and
combining function cai2021rethinking ; zhang2021automated , that hold promise
for discovering novel message passing mechanisms. The existing graph NAS
methods mainly focus on learning effective entity embeddings, but ignore the
latent high-order information associated with edges. In fact, mining the
relation information concealed in the edges can guide fine-grained message
passing on graph and enrich graph search space, which is beneficial to node-
level, edge-level and graph-level tasks.

Recently, increasing manually-designed GNNs chen2021edge ; jiang2019censnet ;
Li_2019_CVPR ; yang2020nenn try to incorporate edge features into models for
better exploiting relation information. Specifically, they stack the building
layers in a sequential architecture and iteratively learn features of entity
and edge. Nevertheless, such plain architecture follows incremental updating
rule based on current layer’s representation, which is naive and sub-optimal.
Also, these approaches adopt simple edge learning function, which is difficult
to learn high-order and long-term relation features.

In this paper, we propose Edge-featured Graph Neural Architecture Search
(EGNAS) with novel edge-featured search space to learn the optimal GNN
architecture using gradient-based search strategy. Our search space (shown in
Figure 1(b)) treats edge as entity-equivalent and adopts dual updating graph
as architecture topology to learn the high-order representations of entity and
edge, which presents more generic message passing mechanisms. Specifically, it
models multi levels of entity and edge features, and allows complex dependence
among them rather than classical sequential structure. Further, we design two
kind of atomic operations: (1) entity updating operations for aggregating
neighboring messages guided by relation features, (2) edge updating operations
for modeling higher order relations guided by entity features. Based on the
differentiable search algorithm, we can efficiently find the optimal
dependence graph and updating operations to construct final GNN. Experiments
at six benchmarks show our EGNAS can search better GNNs with higher
performance than current state-of-the-art methods, including hand-designed and
searched-based GNNs.

Our contributions can be summarized as follows:

  * •

We present edge-featured graph neural architecture search to find the optimal
graph neural architecture, where a novel search space is designed with rich
entity and edge updating operations.

  * •

This is the first effort that explicitly incorporates edge features into graph
search space, where dual updating graph is introduced to explore complex
entity/edge feature dependence and learn high-order representations,
presenting more generic message passing mechanisms.

  * •

We evaluate EGNAS on six benchmarks at three typical graph tasks. The results
show that graph architectures searched by EGNAS outperform the human-invented
and search-based architectures.

Figure 1: A comparison between the traditional cell-based graph search space
and our proposed edge-featured graph search space with dual updating graph of
entity and edge.

##  2 Related Work

Graph Neural Networks. GNNs have been successfully applied to operate on the
graph-structure data bresson2017residual ; brockschmidt2020gnn ;
corso2020principal ; kipf2016semi ; li2015gated ; NEURIPS2020_1534b76d ;
velivckovic2017graph ; vignac2020building ; xu2018powerful ;
yang2020factorizable . Current GNNs are constructed on message passing
mechanisms and can be categorized into two groups, isotropic and anisotropic.
Isotropic GNNs hamilton2017inductive ; kipf2016semi ; li2015gated ;
vignac2020building ; xu2018powerful aim at extending the original convolution
operation to graphs. Anisotropic GNNs enhance the original models with
anisotropic operations on graphs perona1990scale , such as gating and
attention mechanism battaglia2016interaction ; bresson2017residual ;
marcheggiani2017encoding ; monti2017geometric ; velivckovic2017graph ;
yang2020factorizable . Anisotropic methods usually achieve better performance,
since they can adaptively weight the edges according to the entity features
and guide the message passing. However, these methods over-emphasize on entity
rather than edge features.

Exploiting Edge Features. Recently, researchers chen2021edge ;
jiang2019censnet ; Li_2019_CVPR ; schlichtkrull2018modeling ; yang2020nenn
have tried to intergrate edge features into GNN architecture. Schlichtkrull et
al. schlichtkrull2018modeling propose R-GCNs to model relational data by
grouping edges on graph, which indicates the edges cannot include continuous
attributes. Works chen2021edge ; jiang2019censnet ; yang2020nenn assign high-
dimensional feature for edges and iteratively update edge features using the
same way as entity updating. These methods take no account of the dependencies
between multi-level relation features and lack of diversified update functions
to compute the edge features.

Neural Architecture Search. NAS aims at finding the optimal nerural
architectures specific to dataset baker2016designing ; cai2018proxylessnas ;
chu2020darts ; li2020sgas ; liang2019darts+ ; liu2018darts ; pham2018efficient
; xie2018snas ; zoph2016neural . Search space and search strategy are the most
essential components in NAS. Search space defines which architectures can be
represented in principal. Search strategy details how to explore the search
space. Methods can be mainly categorized into three groups, reinforcement
learning (RL) baker2016designing ; zoph2016neural ; zoph2018learning ,
evolutionary algorithms (EA) liu2017hierarchical ; real2019regularized ;
real2017large and gradient-based (GB) liu2018darts ; xu2019pc ;
zela2019understanding . Due to the success in CNNs and RNNs, recent
researchers cai2021rethinking ; gao2020graph ; jiang2020graph ; lai2020policy
; nunes2020neural ; zhang2021automated ; zhou2019auto apply NAS in graph
machine learning domain to automatically design GNNs, termed as graph neural
architecture search. Most of these works mainly focus on designing graph
search space that can process non-euclidean data. However, during designing
search space, they all ignore the information associated with edges that can
be beneficial to graph tasks. To our best knowledge, we are the first to
explicitly model edge features in graph NAS problem.

Figure 2:  Illustration of entity updating operation and edge updating
operation. “F” module in subfigure (a) is used for processing messages based
on feature-wise linear modulating operation before aggregating.

##  3 Method

In this section, we first formulate the problem of graph neural architecture
search, then introduce edge-featured graph search space and entity/edge
updating operations. Next, we discuss the gradient-based search algorithm.
Finally, we describe how to design final layers based on the specific task.

###  3.1 Problem Statement

We formally define the graph neural architecture search as following bi-level
optimization problem. Given graph search space $\mathcal{A}$, we aim to find
the optimal GNN architecture $\alpha^{*}\in\mathcal{A}$ that minimizes the
validation loss $\mathcal{L}_{val}(w^{*}(\alpha),\alpha^{*})$. The trainable
weights $w^{*}$ associated with the architecture are obtained by minimizing
the training loss $\mathcal{L}_{train}(w^{*},\alpha^{*})$. Mathematically, it
is written as follows.

$\displaystyle{\alpha}^{*}$
$\displaystyle=\mathop{argmin}\limits_{\alpha\in\mathcal{A}}\mathcal{L}_{val}(w^{*}(\alpha),\alpha)$
(1) $\displaystyle w^{*}(\alpha)$
$\displaystyle=\mathop{argmin}\limits_{w}\mathcal{L}_{train}(w,\alpha)$ (2)

The characteristic of GNN search problem is that the search space
$\mathcal{A}$ consists of atomic operations which are designed to process
complex graph-structure data and convey rich message passing mechanisms.

###  3.2 Search Space

Similar to the search space of CNNs, we search computational cells as the
building blocks and stack them for the final model (shown in Figure 1(b)). In
our edge-featured search space, each computational cell consists of dual
directed acyclic graphs, termed as entity-updating graph and edge-updating
graph. In the following, we will describe how the two graphs are constructed.

Entity-updating Graph. Entity-updating graph consists of an ordered sequence
of $N$ nodes. Each node $\bm{V}_{i}$ is latent representations (_i.e._ entity
embeddings in a GNN layer) and each directed edge $(i,j)$ is associated with
some entity-updating operation $o_{\mathcal{V}}^{(i,j)}$ that transforms
$\bm{V}_{i}$ to $\bm{V}_{j}$ guided by relation features $\bm{E}_{i}$ (shown
in Figure2(a)). We compute each imtermediate node based on all its
predecessors, written as

$\bm{V}_{j}=\sum_{0\leq i<j}o_{\mathcal{V}}^{(i,j)}(\bm{V}_{i},\bm{E}_{i}),$
(3)

where $1\leq j\leq N$, $\bm{V}_{0}$ denotes the input entity representation.
Inspired by works brockschmidt2020gnn ; perez2018film , we use relation
representation as input that determines an element-wise affine transformation
of incoming messages. This allows the model to dynamically up-weight and down-
weight features based on the information of relation. It yields the following
update rule,

$\displaystyle\bm{\beta}^{(s,t)},\bm{\gamma}^{(s,t)}=g(\bm{E}^{(s,t)}_{i};\bm{\theta}_{i}),$
(4)
$\displaystyle\bm{V}_{j}^{(t)}=\mathcal{M}(\\{\bm{\gamma}^{(s,t)}\odot\bm{V}_{j}^{(s)}+\bm{\beta}^{(s,t)}|s\in\mathcal{N}(t)\\}),$
(5)

where $g(\cdot)$ is a function to compute affine transformation,
$\bm{\theta}_{i}$ is learnable parameters, $\mathcal{N}(t)$ denotes
neighboring entities of target entity $t$. We define optional message
aggregator $\mathcal{M}(\cdot)$ as a continuous function of multisets that
aggregates messages on neighboring entities, such as $\mathop{sum}$,
$\mathop{mean}$ and $\mathop{max}$. Different aggregators capture different
types of information, work cai2021rethinking demonstrates that $\mathop{sum}$,
$\mathop{mean}$, and $\mathop{max}$ do well in capturing structural,
statistical and representative information from neighboring entities,
respectively. Our search space allows to select the most appropriate message
aggregators for different graph datasets. Besides, we introduce _entity skip-
connect_ operation in search space to alleviate the gradient vanishing and
over-smoothing problems. The output of the whole entity-updating graph is
obtained by applying a reduction operation (_e.g._ concatenation) to all the
intermediate nodes.

Edge-updating Graph. Edge-updating graph is a directed acyclic graph with the
same number of nodes but different topology as entity-updating graph. Each
node $\bm{E}_{i}$ is the latent relation representation and each directed edge
$(i,j)$ is associated with some edge-updating operation
$o^{(i,j)}_{\mathcal{E}}$ that learns higher order relation representation
$\bm{E}_{j}$ from both $\bm{E}_{i}$ and its corresponding entity
representation $\bm{V}_{i}$ (shown in Figure2(b)). Similarly, the intermediate
node in edge-updating graph follows below update rule,

$\bm{E}_{j}=\sum_{0\leq i<j}o_{\mathcal{E}}^{(i,j)}(\bm{E}_{i},\bm{V}_{i}),$
(6)

where $1\leq j\leq N$, $\bm{E}_{0}$ denotes the input relation representation.
Note that, if there is no original relation representation in datasets, then
$\bm{E}_{0}$ is initialized with identity vectors $\bm{1}=[1]$. Specifically,
for two entities $s$ and $t$, we first compute the joint entity representation
as temporary relation feature $[\bm{V}^{(s)}_{i}\parallel\bm{V}^{(t)}_{i}]$,
then use it to update current relation representation $\bm{E}^{(s,t)}_{i}$:

$\bm{E}^{(s,t)}_{j}=\mathcal{U}(\bm{E}^{(s,t)}_{i},[\bm{V}^{(s)}_{i}\parallel\bm{V}^{(t)}_{i}])$
(7)

where $\parallel$ denotes concatenation operation, $\mathcal{U}(\cdot,\cdot)$
is an optional updating function. To present more message passing mechanisms,
we introduce several update functions with different capabilities, such as
_Concat_ , _FiLM_ perez2018film and _GRU_ chung2014empirical . _Concat_
denotes concatenation, that is the naivest operation of feature aggregation.
_FiLM_ is short for feature-wise linear modulation that dynamically up-weight
or down-weight old relation feature guided by temporary relation feature.
_GRU_ adaptively determines how much old relation feature to forget and how
much temporary relation features to inject. This is critical for preserving
long-term relation and constructing robust high-order relation features.
Besides, we also introduce a special operation _edge skip-connect_ to improve
learning deep relation features. The output of the edge-updating graph is also
obtained by applying a reduction operation to all the intermediate nodes.
222All the candidate operations and computation details can be found in
supplementary material.

###  3.3 Search Strategy

Following previous works cai2021rethinking ; li2020sgas , we adopt
differentiable NAS strategy to find the optimal GNN. Instead of optimizing
different operations separately, differentiable strategy maintains a supernet
(one-shot model) containing all candidate operations, formally written as

$\bar{o}^{(i,j)}(x)=\sum_{o\in\mathcal{O}}\frac{exp(\alpha^{(i,j)}_{o})}{\sum_{o^{\prime}\in\mathcal{O}}exp(\alpha^{(i,j)}_{o^{\prime}})}o(x),$
(8)

where $\mathcal{O}$ is a set of candidate operations, $\alpha^{(i,j)}$ is
learnable vector that controls which operation is selected. Briefly, each
mixed operation $\bar{o}^{(i,j)}$ is regarded as a probability distribution of
all possible operations. In this way, we can use gradient-based algorithms to
jointly optimize the architecture and model weights. At the end of search, a
discrete architecture is derived from supernet by replacing each mixed
operation $\bar{o}^{(i,j)}$ with the most likely operation, i.e.,
$o^{(i,j)}=\mathop{argmax}_{o\in\mathcal{O}}\alpha^{(i,j)}_{o}$. For each node
in cell, we retain at most two edges from all of its incoming edges.
$\mathcal{O}$ can either be entity updating operation set
$\mathcal{O}_{\mathcal{V}}$ or edge updating operation set
$\mathcal{O}_{\mathcal{E}}$.

###  3.4 Task-based Layer

We design the final network layers depending on the specific task. Let
$\mathcal{V}=\\{v_{1},v_{2},...,v_{|\mathcal{V}|}\\}$ be the set of entities
and $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ be the set of edges,
$\bm{V}_{o}\in\mathbb{R}^{|\mathcal{V}|\times
d_{\mathcal{V}}},\bm{E}_{o}\in\mathbb{R}^{|\mathcal{E}|\times
d_{\mathcal{E}}}$ be the final entity representation and edge (relation)
representation, respectively.

Node-level task layer. For node classification task, the prediction
$\bm{y}^{(i)}_{\mathcal{V}}$ is done as follows:

$\bm{y}^{(i)}_{\mathcal{V}}=\bm{P}_{\mathcal{V}}\bm{V}^{(i)}_{o}$ (9)

where $\bm{P}_{\mathcal{V}}\in\mathbb{R}^{C\times d_{\mathcal{V}}}$ is the
classifier, $C$ is the number of entity classes.

Edge-level task layer. For edge classification task, our method naturally
makes predictions based on deep edge features $\bm{E}_{o}$, formally written
as

$\bm{y}^{(s,t)}_{\mathcal{E}}=\bm{P}_{\mathcal{E}}\bm{E}^{(s,t)}_{o}$ (10)

where $\bm{P}_{\mathcal{E}}\in\mathbb{R}^{C\times d_{\mathcal{E}}}$ is a
learnable matrix, $C$ is the number of edge classes. This is better than
traditional GNN works kipf2016semi ; xu2018powerful ; velivckovic2017graph
that concatenate the entity features as edge features, since the independent
edge features are more discriminative at edge-level tasks.

Graph-level task layer. For graph classification and regression tasks, we
first use mean-pooling readout operation to compute global entity feature and
global edge feature, then concatenates them as global graph representation.
The prediction $\bm{y}_{\mathcal{G}}$ is computed as follows

$\bm{y}_{\mathcal{G}}=\bm{P}_{\mathcal{G}}\big{[}\frac{1}{|\mathcal{V}|}\sum_{i\in\mathcal{V}}\bm{V}^{(i)}_{o}\big{|}\big{|}\frac{1}{|\mathcal{E}|}\sum_{(s,t)\in\mathcal{E}}\bm{E}^{(s,t)}_{o}\big{]},$
(11)

where
$\bm{P}_{\mathcal{G}}\in\mathbb{R}^{C\times(d_{\mathcal{V}}+d_{\mathcal{E}})}$
is a learnable transformation matrix, $C$ is the number of graph classes.

##  4 Experiments

###  4.1 Experimental Setups

Datasets. We evaluate our method on six datasets (TSP, ZINC irwin2012zinc ,
MNIST lecun1998gradient , CIFAR10, PATTERN dwivedi2020benchmarking and CLUSTER
dwivedi2020benchmarking ) across three different level tasks (edge-level,
graph-level and node-level). TSP dataset is based on the classical _Travelling
Salesman Problem_ , which tests edge classification on 2D Euclidean graphs to
indentify edges belonging to the optimal TSP solution. ZINC is one popular
real-world molecular dataset of 250K graphs, whose task is graph property
regression, out of which we select 12K for efficiency following works
cai2021rethinking ; corso2020principal ; dwivedi2020benchmarking . MNIST and
CIFAR10 are original classical image classification datasets and converted
into graphs using superpixel achanta2012slic algorithm to test graph
classification task. PATTERN and CLUSTER are node classification tasks
generated via Stochastic Block Models abbe2017community , which are used to
model communications in social networks by modulating the intra-community and
extra-community connections. Details about the six datasets are shown in Table
LABEL:tab_summary, where $\mathcal{V},\mathcal{E},\mathcal{G}$ denote node-
level, edge-level and graph-level tasks, respectively.

Searching settings. In EGNAS, we define entity updating operation set
$\mathcal{O}_{\mathcal{V}}$: _sum_ , _max_ , _mean_ , _entity skip-connect_
and _zero_ , edge updating operation set $\mathcal{O}_{\mathcal{E}}$: _Concat_
, _GRU_ , _FiLM_ , _edge skip-connect_ and _zero_. Unless otherwise stated,
each operation except _skip-connect_ and _zero_ is followed by a FC-ReLU-BN
module. For fair comparison, on MNIST and CIFAR10, the search space consists
of one computational cell. For other datasets, the search space consists of 4
cells. Each cell consists of 4 entity features and 4 edge features. In order
to stablelize the gradient, additional residual connections are introduced in
each computational cell. To carry out the architecture search, we hold out
half of the training data as validation set. The supernet is trained using
EGNAS for $40$ epochs, with batch size $64$ (for both the training and
validation set). We use momentum SGD to optimize the weights $\bm{w}$, with
initial learning rate $\eta_{\bm{w}}=0.025$ (anneald down to zero following a
cosine schedule without restart), momentum $0.9$, and weight decay $3\times
10^{-4}$. We use Adam kingma2014adam as the optimizer for $\bm{\bm{\alpha}}$,
with initial learning rate $\eta_{\alpha}=3\times 10^{-4}$, momentum
$\beta=(0.5,0.999)$ and weight decay $10^{-3}$.

Training settings. For fair comparison, we follow all training settings (data
splits, optimizer, metrics, etc) in work cai2021rethinking ;
dwivedi2020benchmarking . Specifically, we adopt Adam kingma2014adam with the
same learning rate decay for all runs. The learning rate is initialized with
$10^{-3}$, which is reduced by half if the validation loss stop decreasing
after 10 epochs. During training on CIFAR10 and MNIST dataset, we set dropout
to 0.2 to alleviate the overfitting. For MNIST and CIFAR10 datasets, we report
the results of state-of-the-art GNNs with 4 layers. According to the searching
settings, for other datasets, the GNNs with 16 layers are compared. These
experiments (including searching and training) are run on NVIDIA GTX 2080Ti.
Additional details can be found in the supplementary materials.

###  4.2 Results of Graph-level Task

To test the capacity of our method at graph-level tasks, we assess it on
MNIST, CIFAR10 (both are graph classification task) and ZINC (graph regression
task) datasets. The experimental results are reported in Table LABEL:tab_graph
and Table LABEL:tab_ZINC_TSP. We observe that, first, our method surpasses all
the state-of-the-art hand-designed and search-based GNNs by a large margin
($17.5\%\uparrow$ on ZINC, $3.8\%\uparrow$ on CIFAR10, $0.3\%\uparrow$ on
MNIST), which demonstrates the effectiveness of EGNAS. Compared with the
previous GNAS approaches cai2021rethinking ; gao2020graph , our EGNAS achieves
a great performance improvement with fewer parameters. This indicates that our
designed search space with more efficient atomic operations is better than
traditional graph search space, and the searched GNN has more compact graph
architecture. Second, the performance of EGNAS without edge features degrades
significantly, proving that exploiting relation information in edges is
critical for learning better graph representations. Even on CIFAR10 and MNIST
datasets whose edges only describe binary topological connections, our EGNAS
still mines latent relation to guide better message passing on graph.

###  4.3 Results of Edge-level Task

We compare the performance of our optimal searched architecture with state-of-
the-art hand-designed and search-based GNNs on TSP dataset. The results are
presented in Table LABEL:tab_ZINC_TSP. We observe that GNNs incorporating edge
features significantly outperform those only focusing on learning entity
features, where the latter velivckovic2017graph ; cai2021rethinking obtain the
representation of edges for final classification by concatenating entity
features. This indicates that at the task of edge classification, assigning
independent features to each edge can reduce its dependence on the entity
features, and thus improve the discriminability of edge representations. In
addition, the optimal GNN architecture discovered by our EGNAS surpasses the
state-of-the-art GatedGCN bresson2017residual , which reflects the
effectiveness of EGNAS at edge-level tasks. The performance improvement
benefits from that our dual updating graph facilitates to explore more generic
message passing mechanisms.

###  4.4 Results of Node-level Task

We show the results at node classification task on PATTERN and CLUSTER
datasets in Table LABEL:tab_node. PATTERN dataset tests the fundamental graph
task of recognizing specific predetermined subgraphs, and the CLUSTER dataset
aims at identifying community clusters, where structural information matters.
Notably, the graphs in these datasets represent community networks, in which
the edge only plays role in connecting two nodes. Interestingly, we find that
our EGNAS still achieves competitive performance on PATTERN and surpasses all
the state-of-the-art GNNs on CLUSTER. Actually, the message propagation
through intra-community and extra-community connections should be different on
CLUSTER. The GNNs searched by EGNAS can still distinguish intra-community and
extra-community connections through mining local structural similarities
between nodes. Specifically, they model structural similarity information in
edge features using edge updating operations, to guide message passing and
help identify specific communities on graph.

###  4.5 Ablation Study for Architectures

Figure 3:  Experiments of modifying searched GNN architecture on ZINC dataset.
Baseline architecture is the best GNN architecture searched by the EGNAS, the
others are obtained by modifying baseline architecture based on different
rules, such as replacing entity updating operation (left), edge updating
operation (middle) and modifying architecture topology (right).

Here, we explore what happens if we make some changes to the optimal searched
architecture, which is termed as “Baseline” architecture. First, we study the
impact of the replacement of atomic operations. Specifically, we replace all
the entity updating operations in “Baseline” architecture with a specific
operation (_e.g._ _Mean_ , _Max_ , _Sum_), with other operations unchanged,
obtaining three modified architectures. Similarly, we replace all the edge
updating operations in “Baseline” architecture with _Conat_ , _GRU_ and _FiLM_
operations, respectively, for ablations of edge updating operations. These six
architectures are retrained on ZINC dataset and the test performance in terms
of MAE is shown in Figure 3 (left and middle). We can observe that both
convergence speed and MAE of the modified architectures are worse than the
“Baseline” architecture, which means that the representation ability of a
single feature updating operation is limited. Further, our method can
automatically search the optimal way to combine different entity/edge updating
operations, discovering novel message passing mechanisms and enhancing the
graph representation learning capability of GNN.

Second, we study the impact of architecture topology (feature dependence
graph). We randomly sample a graph neural architecture from edge-featured
graph search space, termed as “Random”. Besides, we obtain a “Sequential”
architecture by removing some edges from edge-updating graph of “Baseline”
architecture to make sure that $\bm{E}_{i}$ just depends on $\bm{E}_{i-1}$.
Experimental results (the right of Figure 3) show that “Random” is better than
“Sequential” but worse than “Baseline” architecture. This emphasizes that
searching complex dependence graph of multi-level edge features matters. It is
also interesting to note that randomly sampled architecture is competitive,
which reflects the importance of the graph search space design.

Figure 4:  Best architecture with 4 cells searched on ZINC dataset. Each
subfigure corresponds to a specific computational cell, in which the above and
below graphs describe edge-updating graph and entity-updating graph,
respectively. Notably, entity updating operations with $(+\bm{E}_{x})$ means
the architecture updates entity features guided by edge features $\bm{E}_{x}$.
Similar, edge updating operations with $(+\bm{V}_{x})$ denotes that the entity
features $\bm{V}_{x}$ are involved in the computation of learning edge
features.

###  4.6 Further Discussion

According to the experiments, we have observed some interesting phenomena that
may inspire the design of edge-featured GNNs. The longest path in the edge
updating graph is getting shorter as the computational cell depth increases
(more nodes directly connect to $\bm{E}_{0}$ with _edge skip-connect_
operation). As depth increases, the edge features are smoothed along with
entity features, weakening the ability to characterize the local structural
similarity. Our EGNAS can automatically detect this phenomenon and supplement
some lower order edge features via extra connections to counteract this
smoothness. Another evidence is that the “Sequential” architecture performs
worse than “Baseline” architecture (shown in the right of Figure 3), where
“Baseline” contains more connections from lower order edge features in deeper
computational cells. The searched architectures on other datasets also show
similar preference. More results can be found in supplementary materials.

##  5 Conclusion

In this paper, we incorporate edge features in graph neural architecture
search for the first time, to find the optimal GNN architecture that can mine
and exploit latent relation information concealed in edges. Specifically, we
design edge-featured graph search space with novel atomic operations, which
allows to explore complex entity/edge feature dependence and presents more
generic message passing mechanisms. Experiments on six benchmarks at three
classical graph tasks demonstrate that our EGNAS rivals all the human-invented
and search-based methods. Further, we analyze the searched optimal
architectures and confirm the effectiveness of our EGNAS.

## Boarder Impact

Our paper proposes edge-featured graph neural architecture search method that
further introduces novel graph search space with more generic message passing
mechanisms and find the optimal GNN architecture. Notably, this is a
significant improvement on designing graph search space. It will have a direct
impact on the application of graph neural networks in the industry. The
positive impacts are described as follows. First, we can efficiently find
better GNN architectures that can mine and exploit the relation information
implied in graph. So the practical application of GNN to the corresponding
area can be fostered. Second, we analyze the optimal searched GNN
architectures and summarize some findings which may have implications for the
design of GNN. Moreover, by applying our EGNAS to different tasks and
datasets, we think that it could bring researchers expertise in understanding
graph neural architectures. There are also some limitations in our method. For
example, we mainly focus on designing generic graph search space rather than
search strategy. We will develop specific search strategies for graph neural
architecture search to improve the efficiency and performance of search in
future works.

## References

  * [1] Emmanuel Abbe.  Community detection and stochastic block models: recent developments.  The Journal of Machine Learning Research, 18(1):6446–6531, 2017\.
  * [2] Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine Süsstrunk.  Slic superpixels compared to state-of-the-art superpixel methods.  IEEE transactions on pattern analysis and machine intelligence, 34(11):2274–2282, 2012.
  * [3] Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar.  Designing neural network architectures using reinforcement learning.  arXiv preprint arXiv:1611.02167, 2016.
  * [4] Peter W Battaglia, Razvan Pascanu, Matthew Lai, Danilo Rezende, and Koray Kavukcuoglu.  Interaction networks for learning about objects, relations and physics.  arXiv preprint arXiv:1612.00222, 2016.
  * [5] Xavier Bresson and Thomas Laurent.  Residual gated graph convnets.  arXiv preprint arXiv:1711.07553, 2017.
  * [6] Marc Brockschmidt.  Gnn-film: Graph neural networks with feature-wise linear modulation.  In International Conference on Machine Learning, pages 1144–1152. PMLR, 2020.
  * [7] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst.  Geometric deep learning: going beyond euclidean data.  IEEE Signal Processing Magazine, 34(4):18–42, 2017.
  * [8] Han Cai, Ligeng Zhu, and Song Han.  Proxylessnas: Direct neural architecture search on target task and hardware.  arXiv preprint arXiv:1812.00332, 2018.
  * [9] Shaofei Cai, Liang Li, Jincan Deng, Beichen Zhang, Zheng-Jun Zha, Li Su, and Qingming Huang.  Rethinking graph neural architecture search from message-passing.  arXiv preprint arXiv:2103.14282, 2021.
  * [10] Jun Chen and Haopeng Chen.  Edge-featured graph attention network.  arXiv preprint arXiv:2101.07671, 2021.
  * [11] Xiangxiang Chu, Xiaoxing Wang, Bo Zhang, Shun Lu, Xiaolin Wei, and Junchi Yan.  Darts-: robustly stepping out of performance collapse without indicators.  arXiv preprint arXiv:2009.01027, 2020.
  * [12] Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio.  Empirical evaluation of gated recurrent neural networks on sequence modeling.  arXiv preprint arXiv:1412.3555, 2014.
  * [13] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković.  Principal neighbourhood aggregation for graph nets.  arXiv preprint arXiv:2004.05718, 2020.
  * [14] Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson.  Benchmarking graph neural networks.  arXiv preprint arXiv:2003.00982, 2020.
  * [15] Yang Gao, Hong Yang, Peng Zhang, Chuan Zhou, and Yue Hu.  Graph neural architecture search.  In IJCAI, volume 20, pages 1403–1409, 2020.
  * [16] William L Hamilton, Rex Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  arXiv preprint arXiv:1706.02216, 2017.
  * [17] John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman.  Zinc: a free tool to discover chemistry for biology.  Journal of chemical information and modeling, 52(7):1757–1768, 2012\.
  * [18] Shengli Jiang and Prasanna Balaprakash.  Graph neural network architecture search for molecular property prediction.  arXiv preprint arXiv:2008.12187, 2020.
  * [19] Xiaodong Jiang, Pengsheng Ji, and Sheng Li.  Censnet: Convolution with edge-node switching in graph neural networks.  In IJCAI, pages 2656–2662, 2019.
  * [20] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [21] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907, 2016.
  * [22] Kwei-Herng Lai, Daochen Zha, Kaixiong Zhou, and Xia Hu.  Policy-gnn: Aggregation optimization for graph neural networks.  In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 461–471, 2020.
  * [23] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [24] Guohao Li, Guocheng Qian, Itzel C Delgadillo, Matthias Muller, Ali Thabet, and Bernard Ghanem.  Sgas: Sequential greedy architecture search.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1620–1630, 2020.
  * [25] Yuchao Li, Shaohui Lin, Baochang Zhang, Jianzhuang Liu, David Doermann, Yongjian Wu, Feiyue Huang, and Rongrong Ji.  Exploiting kernel sparsity and entropy for interpretable cnn compression.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [26] Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel.  Gated graph sequence neural networks.  arXiv preprint arXiv:1511.05493, 2015.
  * [27] Hanwen Liang, Shifeng Zhang, Jiacheng Sun, Xingqiu He, Weiran Huang, Kechen Zhuang, and Zhenguo Li.  Darts+: Improved differentiable architecture search with early stopping.  arXiv preprint arXiv:1909.06035, 2019.
  * [28] Hanxiao Liu, Karen Simonyan, Oriol Vinyals, Chrisantha Fernando, and Koray Kavukcuoglu.  Hierarchical representations for efficient architecture search.  arXiv preprint arXiv:1711.00436, 2017.
  * [29] Hanxiao Liu, Karen Simonyan, and Yiming Yang.  Darts: Differentiable architecture search.  arXiv preprint arXiv:1806.09055, 2018.
  * [30] Diego Marcheggiani and Ivan Titov.  Encoding sentences with graph convolutional networks for semantic role labeling.  arXiv preprint arXiv:1703.04826, 2017.
  * [31] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein.  Geometric deep learning on graphs and manifolds using mixture model cnns.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5115–5124, 2017.
  * [32] Matheus Nunes and Gisele L Pappa.  Neural architecture search in graph neural networks.  In Brazilian Conference on Intelligent Systems, pages 302–317. Springer, 2020.
  * [33] Ethan Perez, Florian Strub, Harm De Vries, Vincent Dumoulin, and Aaron Courville.  Film: Visual reasoning with a general conditioning layer.  In Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
  * [34] Pietro Perona and Jitendra Malik.  Scale-space and edge detection using anisotropic diffusion.  IEEE Transactions on pattern analysis and machine intelligence, 12(7):629–639, 1990.
  * [35] Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean.  Efficient neural architecture search via parameters sharing.  In International Conference on Machine Learning, pages 4095–4104. PMLR, 2018.
  * [36] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le.  Regularized evolution for image classifier architecture search.  In Proceedings of the aaai conference on artificial intelligence, pages 4780–4789, 2019.
  * [37] Esteban Real, Sherry Moore, Andrew Selle, Saurabh Saxena, Yutaka Leon Suematsu, Jie Tan, Quoc V Le, and Alexey Kurakin.  Large-scale evolution of image classifiers.  In International Conference on Machine Learning, pages 2902–2911. PMLR, 2017.
  * [38] Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling.  Modeling relational data with graph convolutional networks.  In European semantic web conference, pages 593–607. Springer, 2018\.
  * [39] Masashi Tsubaki and Teruyasu Mizoguchi.  On the equivalence of molecular graph convolution and molecular wave function with poor basis set.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1982–1993. Curran Associates, Inc., 2020.
  * [40] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  arXiv preprint arXiv:1710.10903, 2017.
  * [41] Clément Vignac, Andreas Loukas, and Pascal Frossard.  Building powerful and equivariant graph neural networks with structural message-passing.  arXiv e-prints, pages arXiv–2006, 2020.
  * [42] Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin.  Snas: stochastic neural architecture search.  arXiv preprint arXiv:1812.09926, 2018.
  * [43] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  In International Conference on Learning Representations, 2018.
  * [44] Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong.  Pc-darts: Partial channel connections for memory-efficient architecture search.  arXiv preprint arXiv:1907.05737, 2019.
  * [45] Yiding Yang, Zunlei Feng, Mingli Song, and Xinchao Wang.  Factorizable graph convolutional networks.  Advances in Neural Information Processing Systems, 33, 2020.
  * [46] Yulei Yang and Dongsheng Li.  Nenn: Incorporate node and edge features in graph neural networks.  In Asian Conference on Machine Learning, pages 593–608. PMLR, 2020\.
  * [47] Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter.  Understanding and robustifying differentiable architecture search.  arXiv preprint arXiv:1909.09656, 2019.
  * [48] Ziwei Zhang, Xin Wang, and Wenwu Zhu.  Automated machine learning on graphs: A survey.  arXiv preprint arXiv:2103.00742, 2021.
  * [49] Kaixiong Zhou, Qingquan Song, Xiao Huang, and Xia Hu.  Auto-gnn: Neural architecture search of graph neural networks.  arXiv preprint arXiv:1909.03184, 2019.
  * [50] Barret Zoph and Quoc V Le.  Neural architecture search with reinforcement learning.  arXiv preprint arXiv:1611.01578, 2016.
  * [51] Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le.  Learning transferable architectures for scalable image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8697–8710, 2018.

##  Appendix A Implementation Details

In this section, we details how entity updating operations and edge updating
operations are formulated. We declare that
$\bm{V}\in\mathbb{R}^{|\mathcal{V}|\times d_{\mathcal{V}}}$ denotes entity
feature, $\bm{E}\in\mathbb{R}^{|\mathcal{E}|\times d_{\mathcal{E}}}$ denotes
edge feature, $\mathcal{V}$ is the set of entities, $\mathcal{E}$ is the set
of edges, $d_{\mathcal{V}}$ is the dimension of entity feature,
$d_{\mathcal{E}}$ is the dimension of edge feature.

###  A.1 Entity Updating Operation

As discussed in body content, we use relation representation as input that
determines an element-wise affine transformation of incoming messages,
allowing the model to dynamically up-weight and down-weight features based on
the information of relation. It yields the following update rule,

$\displaystyle\bm{\beta}^{(s,t)},\bm{\gamma}^{(s,t)}=g(\bm{E}^{(s,t)}_{i};\bm{\theta}_{i}),$
(12)
$\displaystyle\bm{V}_{j}^{(t)}=\mathcal{M}(\\{\bm{\gamma}^{(s,t)}\odot\bm{V}_{j}^{(s)}+\bm{\beta}^{(s,t)}|s\in\mathcal{N}(t)\\}),$
(13)

where $g(\cdot)$ is a function to compute affine transformation,
$\bm{\theta}_{i}$ is learnable parameters, $\mathcal{N}(t)$ denotes
neighboring entities of target entity $t$, $\mathcal{M}$ is an optional
neighbor aggregator. We define _Max_ , _Mean_ , _Sum_ entity updating
operations for aggregating messages, with neighbor aggregator
$\mathcal{M}(\cdot)$ as $max(\cdot)$, $mean(\cdot)$ and $sum(\cdot)$,
respectively. Besides, we also introduce a special operation _entity skip-
connect_ to alleviate the gradient vanishing and over-smoothing problems,
formulated as

$o_{\mathcal{V}\cdot skip}(\bm{V}_{i},\bm{E}_{i})=\bm{V}_{i}.$ (14)

###  A.2 Edge Updating Operation

As we discussed in body content, the edge updating equation can be written as
follows:

$\bm{E}^{(s,t)}_{j}=\mathcal{U}(\bm{E}^{(s,t)}_{i},[\bm{V}^{(s)}_{i}\parallel\bm{V}^{(t)}_{i}])$
(15)

where $\parallel$ denotes the concatenation operation,
$\mathcal{U}(\cdot,\cdot)$ is an optional updating function. Since we define
multiple edge updating operations _Concat_ , _GRU_ , _FiLM_ and _edge skip-
connect_ , the difference between them is the choice of the updating function
$\mathcal{U}(\cdot,\cdot)$.

For _Concat_ Operation.  _Concat_ denotes the concatenation, that is the
naivest operation of feature aggregation. We use the following updating rule:

$\mathop{\mathcal{U}}\limits_{Concat}(\bm{E}^{(s,t)}_{i},[\bm{V}^{(s)}_{i}\parallel\bm{V}^{(t)}_{i}])=MLP([\bm{E}^{(s,t)}_{i}\parallel\bm{V}^{(s)}_{i}\parallel\bm{V}^{(t)}_{i}])$
(16)

where $MLP(\cdot)$ denotes a multi-layer perceptron that obtains new edge
feature with $d_{\mathcal{E}}$ dimension.

For _GRU_ Operation.  _GRU_ [12] adaptively determines how much old relation
feature to forget and how much temporary relation features to inject. This is
critical for preserving long-term relation and constructing robust high-order
relation features. Mathematically, it can be formulated as

$\displaystyle\bm{x}=ReLU(\bm{P}_{x}[\bm{V}^{(s)}_{i}\parallel\bm{V}^{(t)}_{i}])$
(17)
$\displaystyle\bm{r}=\sigma(\bm{U}_{r}\bm{x}+\bm{W}_{r}\bm{E}^{(s,t)}_{i})$
(18)
$\displaystyle\bm{z}=\sigma(\bm{U}_{z}\bm{x}+\bm{W}_{z}\bm{E}^{(s,t)}_{i})$
(19)
$\displaystyle\bm{h}=tanh(\bm{U}_{h}\bm{x}+\bm{W}_{h}(\bm{r}\odot\bm{E}^{(s,t)}_{i}))$
(20)
$\displaystyle\mathop{\mathcal{U}}\limits_{GRU}(\bm{E}^{(s,t)}_{i},[\bm{V}^{(s)}_{i}\parallel\bm{V}^{(t)}_{i}])=(\bm{1}-\bm{z})\odot\bm{E}^{(s,t)}_{i}+\bm{z}\odot\bm{h}$
(21)

where $\bm{P}_{x}\in\mathbb{R}^{d_{\mathcal{E}}\times 2d_{\mathcal{V}}}$,
$\bm{U}_{r}\in\mathbb{R}^{d_{\mathcal{E}}\times d_{\mathcal{E}}}$,
$\bm{W}_{r}\in\mathbb{R}^{d_{\mathcal{E}}\times d_{\mathcal{E}}}$,
$\bm{U}_{z}\in\mathbb{R}^{d_{\mathcal{E}}\times d_{\mathcal{E}}}$,
$\bm{W}_{z}\in\mathbb{R}^{d_{\mathcal{E}}\times d_{\mathcal{E}}}$,
$\bm{U}_{h}\in\mathbb{R}^{d_{\mathcal{E}}\times d_{\mathcal{E}}}$ and
$\bm{W}_{h}\in\mathbb{R}^{d_{\mathcal{E}}\times d_{\mathcal{E}}}$ are
learnable matrices, $ReLU$ is ReLU activation function, $\sigma(\cdot)$ is
sigmoid activation function.

For _FiLM_ Operation.  _FiLM_ is short for feature-wise linear modulation [33]
that dynamically up-weight or down-weight old relation feature guided by
temporary relation feature. The required updating function can be written as

$\displaystyle\bm{\beta}^{(s,t)},\bm{\gamma}^{(s,t)}=g([\bm{V}^{(s)}_{i}\parallel\bm{V}^{(t)}_{i}];\bm{\theta}_{i})$
(22)
$\displaystyle\mathop{\mathcal{U}}\limits_{FiLM}(\bm{E}^{(s,t)}_{i},[\bm{V}^{(s)}_{i}\parallel\bm{V}^{(t)}_{i}])=\bm{\gamma}^{(s,t)}\odot\bm{E}^{(s,t)}_{i}+\bm{\beta}^{(s,t)}$
(23)

where $g(\cdot)$ is a function to compute affine transformation,
$\bm{\theta}_{i}$ is learnable parameters.

For _edge skip-connect_ Operation.  We introduce a special operation _edge
skip-connect_ to improve learning deep relation features, formulated as

$\displaystyle\mathop{\mathcal{U}}\limits_{skip-
connect}(\bm{E}^{(s,t)}_{i},[\bm{V}^{(s)}_{i}\parallel\bm{V}^{(t)}_{i}])=\bm{E}^{(s,t)}_{i}$
(24)

The _skip-connect_ plays role in supplementing low level representations and
alleviating gradient vanishing.

##  Appendix B Architecture Visualization

Figure 5:  Best architecture with 4 cells searched on ZINC dataset.

As a supplementary for Section 4.6 in body content, we visualize the best
searched architecture for each dataset, including ZINC (shown in Figure 5),
TSP (shown in Figure 6), CLUSTER (shown in Figure 7), PATTERN (shown in Figure
8), MNIST (shown in Figure 9[a]) and CIFAR10 (shown in Figure 9[b]). The
visualization results on these datasets show similar preference as discussed
in Section 4.6, _i.e._ , as depth increases, the edge features are smoothed
along with entity features, weakening the ability to characterize the local
structural similarity. Our EGNAS can automatically detect this phenomenon and
supplement some lower order edge features via extra connections to counteract
this smoothness.

Figure 6:  Best architecture with 4 cells searched on TSP dataset.  Figure 7:
Best architecture with 4 cells searched on CLUSTER dataset.  Figure 8:  Best
architecture with 4 cells searched on PATTERN dataset.  Figure 9:  Best
architecture with one cell searched on MNIST and CIFAR10 datasets.

##  Appendix C Extensive Experiments

To evaluate the sensitivity of our method to the size of the receptive field,
we conduct extensive experiments at edge-level task (on TSP dataset) and
graph-level task (on ZINC dataset), then report the results in Table
LABEL:tab_ZINC_TSP_ex. Besides, we also conduct extensive experiments at node-
level task (no both PATTERN and CLUSTER datasets) and report the results in
Table LABEL:tab_node_ex. We can find that, with the increase of receptive
field, the performance of our model becomes better and better. Our method can
achieve competitive results in any receptive field. In addition, through the
ablation studies, we can see that incorporating edge features into search
space is critical for improving performance of searched GNN architectures.


# Regular Algebras of Dimension Four Associated to Coordinate Rings of Rank-
Two Quadrics

###### Abstract.

In this paper, we classify connected graded quadratic Artin-Schelter regular
(AS-regular, henceforth) algebras of global dimension four that have a Hilbert
series the same as that of the polynomial ring on four generators and that map
onto a twisted homogeneous coordinate ring of a rank-two quadric. A twisted
homogeneous coordinate ring is a construction that was defined by Artin, Tate,
and Van den Bergh in [1, 2, 4] in the context of the classification of AS-
regular algebras of global dimension three. In [10, 14], the authors
classified AS-regular algebras of global dimension four that map onto the
twisted homogeneous coordinate ring of a rank-three and a rank-four quadric,
respectively. We expand on their work to include the case of coordinate rings
of a rank-two quadric.

###### Key words and phrases:

Artin-Schelter regular algebra, point scheme, coordinate rings, rank-two
quadric

###### 2020 Mathematics Subject Classification:

14A22,16S37,16S38

Richard G. Chandler
<EMAIL_ADDRESS>

Hung Tran
<EMAIL_ADDRESS>

Padmini Veerapen
<EMAIL_ADDRESS>
and

Xingting Wang
<EMAIL_ADDRESS>

## Introduction

It is widely accepted that Artin-Schelter regular (AS-regular, henceforth)
algebras can be viewed as noncommutative analogues of polynomial rings. These
algebras were defined by Artin and Schelter in 1987 [3]; Artin, Tate and Van
den Bergh [1, 2] classified those of global dimension three using techniques
that became known as noncommutative projective algebraic geometry. In this
paper, our overarching goal is to provide examples that would contribute to
the classification AS-regular algebras of dimension four by utilizing these
geometric techniques.

In [4], Artin and Van den Bergh elaborate on the construction of a
“noncommutative” version of the commutative homogeneous coordinate ring, known
as a twisted homogeneous coordinate ring. As defined in [4, Definition p.
249], a twisted homogeneous coordinate ring, $S$, is given by three pieces of
data, a projective scheme $Q$ defined over a field $\Bbbk$, an automorphism
$\sigma$ of $Q$, and an invertible sheaf on $Q$, that is, we may write $S$ as
$S(Q,\sigma,\mathcal{L})$. In [5, Definition 4.3.1], Rogalski highlights the
fact that if the invertible sheaf $\mathcal{L}$ is $\sigma$-ample, then such
rings are noetherian and finitely generated by [4, Theorem 1.4].

Shelton, Vancliff, and Van Rompay further examine the twisted homogeneous ring
construction in [10, 14] by classifying the quadratic noetherian AS-regular
algebras of dimension four that map onto the twisted homogeneous coordinate
ring of a rank-three and a rank-four quadric in $\mathbb{P}^{3}$. The algebras
are classified by considering whether their point schemes $P$ either strictly
contains a rank-two quadric, that is, $Q\subset P,$ or are exactly a rank-two
quadric, that is, $P=Q$. In the case of the quadric being strictly contained
in the point scheme, it was shown that the algebra is completely determined by
the geometric data and, thus, the defining relations can be directly
recovered. In this paper, we extend their work to twisted homogeneous
coordinate rings of a rank-2 quadric, $Q\subset\mathbb{P}^{3}$.

In Section 1, Theorem 1.5, we prove a result critical to the rest of the
paper. Assuming that $R$ is a quadratic domain with $\Omega\in R_{2}$ and such
that $A/{\langle\Omega\rangle}=S$, we show that $\Omega$ is normal. In Section
2, we identify regular algebras of global dimension four whose point scheme
strictly contains a rank-two quadric. We begin by finding such algebras whose
automorphism on the quadric is the identity and then twist these algebras by a
non-identity automorphism in $\operatorname{Aut}(\mathbb{P}^{3})$; that is, we
twist them via a Zhang twist. In Section 3, we show, in Proposition 3.2, that
when the point scheme of $R$ is exactly a rank-two quadric, then the quadratic
noetherian AS-regular algebras of dimension four are, in fact, central
extensions of AS-regular algebras of dimension three.

##  1\. Preliminaries

######  Notation 1.1.

Let $Q\in\mathbb{P}^{3}$ be a rank-two quadric and fix an automorphism $\tau$
of $Q$. By $S(Q)$, we mean the (commutative) homogeneous coordinate ring of
$Q$. By $S$, we mean the twisted homogeneous coordinate ring corresponding to
a rank-2 quadric $Q$, an automorphism $\tau$ of $Q$ and a $\tau$–ample
invertible sheaf $\mathcal{L}$, that is, $S=S(Q,\tau,\mathcal{L})$. The set
$\mathcal{R}(Q,\tau)$ consists of all graded algebras $R$ that are quadratic
connected Artin-Schelter regular of global dimension four with Hilbert series
$1/(1-t)^{-4}$ and such that there is a graded degree zero homomorphism
mapping $R$ onto $S$. We denote $R\in\mathcal{R}(Q,\tau)$ by $T(V)/I$ where
$V$ is a four-dimensional vector space, $T(V)$ is the tensor algebra on $V$
and $I$ is a finitely generated graded ideal. The graph of $\tau$ on $Q$ will
be denoted by $\Gamma_{\tau}(Q)$.

In [10, Lemma 1.3], if $A$ is Artin-Schelter regular of global dimension four
with four linearly independent generators, then $A$ is Koszul and has Hilbert
series $H_{A}(t)=(1-t)^{-4}$. In particular, $A$ is quadratic with six
defining relations and has Gelfand-Kirillov dimension four. Henceforth, we
write $R$ as $R=T(V)/W$ where $W$ is a six-dimensional vector space spanned by
the defining relations of $R$.

######  Remark 1.2.

  1. (1)

Using an argument similar to [10, Lemma 1.7], we note that the Hilbert series
of a twisted homogeneous coordinate ring $S$ of any quadric
$Q^{\prime}\in\mathbb{P}^{3}$ is $(1+t)(1-t)^{-3}$. This follows from the fact
that we may view $S$ as a quotient of $S(\mathbb{P}^{3})$ by the ideal
generated by $Q^{\prime}$. As a result, the Hilbert series of $S$ is that of
$Q^{\prime}$ subtracted from that of $S(\mathbb{P}^{3})$ which is given by
$(1-t)^{-4}-t^{2}(1-t)^{-4}$. In general, we will use $S($–$)$ to mean the
(commutative) homogeneous coordinate ring corresponding to that scheme.

  2. (2)

By hypothesis, $R$ has Hilbert series $(1+t)^{-4}$ and maps onto $S$ with
Hilbert series $(1+t)(1-t)^{-3}$. Similar to [14, before Definition 1.3], this
implies that there exists $\Omega\in R_{2}$ such that
$R/{\langle\Omega\rangle}\cong S$. Now, we know that there are no nonzero
elements of $S_{2}$ that vanish on the graph of $\tau$, as $S$ is a domain, so
any nonzero element of $R_{2}$ that vanishes on $\tau$ must be a scalar
multiple of $\Omega$. Thus, for any $u,v\in R_{1}$, $u^{\tau}v-v^{\tau}u\in
R_{2}$ and is a scalar multiple of $\Omega$.

######  Example 1.3.

Let $A$ be the ${\Bbbk}$-algebra given by the polynomial ring
${\Bbbk}[x_{1},x_{2},x_{3},x_{4}]$ subject to the following defining relations

$\begin{matrix}x_{1}x_{2}-x_{2}x_{1},&x_{1}x_{3}-x_{3}x_{1},&x_{1}x_{4}-x_{4}x_{1},&x_{2}x_{4}-x_{4}x_{2},&x_{3}x_{4}-x_{4}x_{3},&x_{1}x_{2}.\end{matrix}$

This algebra is not noetherian since the following chain of right ideals does
not stablize:

$x_{2}A\subset x_{2}A+x_{3}x_{2}A\subset
x_{2}A+x_{3}x_{2}A+x_{3}^{2}x_{2}A\subset\cdots\subset\sum_{i=0}^{n}x_{3}^{i}x_{2}A\subset\cdots$

However, $A/\langle\Omega\rangle$, where $\Omega=x_{2}x_{3}-x_{3}x_{2}\in A$,
is the coordinate ring of the rank-two quadric $\mathcal{V}(x_{1}x_{2})$,
which is noetherian. Therefore, [1, Lemma 8.2] implies that $\Omega$ is not
normal in $A$.

######  Remark 1.4.

  1. (1)

By Example 1.3, we see that, in general, for a quadratic element $\Omega\in
R_{2}$, $R/{\langle\Omega\rangle}\cong S$ does not ensure that $\Omega$ is
normal. This is in agreement with [10, Example 1.6] when the quadric is rank-
three but differs from [14, Lemma 1.5] when the quadric is rank-four.

  2. (2)

By [15, Theorems 3.1 & 3.5], when a connected graded algebra $A$ is twisted by
an automorphism or by a twisting system of $A$ denoted by $\phi$, then the
category of graded modules of $A$, $\operatorname{Gr}A$, and that of graded
modules over $A^{\phi}$, $\operatorname{Gr}A^{\phi}$, are equivalent; that is,
the category of graded modules of $A$ are invariant under twists by
automorphisms and twisting systems. Additionally, by [15, Theorem 1.4], since
$\operatorname{QGr}A$ is equivalent to $\operatorname{QGr}A^{\phi}$, it
follows that the point schemes of $A$ and $A^{\phi}$ are equivalent, where
$\operatorname{QGr}A$, is the quotient category $\operatorname{Gr}A/\mbox{tors
}A$ and tors $A$ is the full subcategory of $\operatorname{Gr}A$ consisting of
modules which are finite dimensional. The global dimension and Hilbert series
of $A$ and $A^{\phi}$ also remain invariant. We refer to the algebras $A$ and
$A^{\phi}$ as Zhang twists of each other as suggested by other authors (see
e.g., [11]).

######  Proposition 1.5.

If $A$ is a quadratic domain with $\Omega\in A_{2}$ such that
$A/\langle\Omega\rangle=S$, then $\Omega$ is normal in $A$.

###### Proof..

In this proof, we use techniques similar to [10, Lemma 1.7] with significant
modifications. By Remark 1.2, we may assume that $\tau=\operatorname{id}$,
that is, $S=S(Q)$, and $uv-vu\in{\Bbbk}\Omega$ for all $u,v\in A_{1}$. Let
$Q=\mathcal{V}(X_{1}X_{2})$, where $X_{1},X_{2}\in A_{1}$ are linearly
independent, and $X_{3}\in A_{1}$ such that
$X_{3}\notin\Bbbk^{\times}X_{1}\oplus\Bbbk^{\times}X_{2}$. It follows that
$X_{i}X_{j}-X_{j}X_{i}=\alpha_{ij}\Omega$ for $\alpha_{ij}\in{\Bbbk}$,
$i,j\in\\{1,2,3\\}$. Define
$y=\alpha_{23}X_{1}-\alpha_{13}X_{2}+\alpha_{12}X_{3}$. It can be verified
that $y$ commutes in $A$ with all elements of the form
${\Bbbk}X_{1}+{\Bbbk}X_{2}+{\Bbbk}X_{3}$. Note also that
$X_{1}X_{2}\in{\Bbbk}^{\times}\Omega$, as it is an element of $A_{2}$ that
vanishes on the graph of $Q$ and is nonzero since $A$ is a domain; thus,
$\Omega\in{\Bbbk}^{\times}X_{1}X_{2}$. Observe that the plane
$\mathcal{V}(y)\subset\mathbb{P}^{3}$ meets $Q$ either in two lines, counted
with multiplicity, or in a plane.

If $\mathcal{V}(y)$ meets $Q$ in two lines, counted with multiplicity, then we
may present $A$ using generators $x_{1}=X_{1}$, $x_{2}=X_{2}$, and $x_{3}=y$
and so, $x_{1}x_{3}=x_{3}x_{1}$ and $x_{2}x_{3}=x_{3}x_{2}$. Moreover, if
$\alpha_{12}=0$, that is, if $x_{1}x_{2}=x_{2}x_{1}$, then $\Omega$ commutes
with $x_{1}$, $x_{2}$ and $x_{3}$. Additionally, if $x_{4}\in
A_{1}\setminus({\Bbbk}x_{1}+{\Bbbk}x_{2}+{\Bbbk}x_{3})$, then

$\displaystyle x_{4}\Omega$ $\displaystyle=x_{4}(\beta
x_{1}x_{2}),\qquad\mbox{ where }\Omega=\beta x_{1}x_{2}$
$\displaystyle=\beta(x_{1}x_{4}+\gamma\Omega)x_{2}$
$\displaystyle=\beta(x_{1}(x_{2}x_{4}+\delta\Omega)+\gamma\Omega x_{2})$
$\displaystyle=\Omega(x_{4}+\beta\delta x_{1}+\beta\gamma x_{2}),$

where $\gamma,\delta\in{\Bbbk}$, that it, $\Omega$ is normal in $A$.
Otherwise, $\alpha_{12}\neq 0$, that is, $x_{1}x_{2}\neq x_{2}x_{1}$, and we
show there is $x_{4}\in
A_{1}\setminus({\Bbbk}x_{1}+{\Bbbk}x_{2}+{\Bbbk}x_{3}$) such that
$x_{1}x_{4}=x_{4}x_{1}$ and $x_{2}x_{4}=x_{4}x_{2}$. Choose $w\in
A_{1}\setminus({\Bbbk}x_{1}+{\Bbbk}x_{2}+{\Bbbk}x_{3}$). If $w$ commutes with
$x_{1}$, define $z=w$; otherwise $x_{1}w-wx_{1}=\beta\Omega$, for
$\beta\in{\Bbbk}^{\times}$. In this case, define $z=\alpha_{12}w-\beta x_{2}$;
in either case, $z$ commutes with $x_{1}$. If, in addition, $z$ commutes with
$x_{2}$, define $x_{4}=z$. Otherwise, $x_{2}z-zx_{2}=\gamma\Omega$, for some
$\gamma\in{\Bbbk}^{\times}$; define $x_{4}=\alpha_{12}z+\gamma x_{1}$. This
$x_{4}$ commutes with $x_{2}$ (and with $x_{1})$, so we may always find an
$x_{4}$ as described above. It follows that $\Omega$ is normal in $A$.

If $\mathcal{V}(y)$ meets $Q$ in a plane, then we may assume without loss of
generality that $y=\alpha_{23}X_{1}$. That is, $\alpha_{13}=0=\alpha_{12}$ and
the defining relations of $A$ include $X_{1}X_{2}=X_{2}X_{1}$,
$X_{1}X_{3}=X_{3}X_{1}$, and $X_{2}X_{3}-X_{3}X_{2}=\alpha_{23}\Omega$. Choose
$w\in A_{1}\setminus({\Bbbk}X_{1}+{\Bbbk}X_{2}+{\Bbbk}X_{3}$). If $w$ commutes
with $X_{3}$, define $z=w$; otherwise $X_{3}w-wX_{3}=\beta\Omega$, for
$\beta\in{\Bbbk}^{\times}$. In this case, define $z=\alpha_{23}w+\beta X_{2}$;
in either case, $z$ commutes with $X_{3}$. If, in addition, $z$ commutes with
$X_{2}$, define $X_{4}=z$. Otherwise, $X_{2}z-zX_{2}=\gamma\Omega$, for some
$\gamma\in{\Bbbk}^{\times}$; define $X_{4}=\alpha_{23}z-\gamma X_{3}$. As
chosen, $X_{4}$ commutes with $X_{2}$ (and with $X_{3})$, so we may always
find an $X_{4}$ as described above. It follows that $\Omega$ is normal in $A$.
∎

##  2\. Regular Algebras whose Point Scheme is not the Union of Two Planes

######  Remark 2.1.

Since $R$ is AS-regular with Hilbert series $H_{R}(t)=(1-t)^{-4}$, by [9,
Definition in §5.8, Corollary in §6.2], we may assume $A$ is a quadratic
noetherian algebra satisfying

  1. (1)

$H_{A}(t)=(1-t)^{-4}$;

  2. (2)

$A$ is Auslander-regular of global dimension four;

  3. (3)

$A$ satisfies the Cohen-Macaulay property.

######  Lemma 2.2.

Let $x_{i}$ and $x_{j}$ be two degree-one elements in $R$. If $x_{i}$ and
$x_{j}$ are both normal in $R$, then $x_{i}x_{j}=\alpha_{ij}x_{j}x_{i}$, for
some $\alpha_{ij}\in{\Bbbk}^{\times}$.

###### Proof..

Since $x_{1}$ and $x_{2}$ are two normal elements in the quadratic algebra
$R$, it follows that $x_{1}x_{2}\in R_{1}x_{1}\cap x_{2}R_{1}$ and
$x_{2}x_{1}\in R_{1}x_{2}\cap x_{1}R_{1}$; hence,
$x_{1}x_{2}\in{\Bbbk}^{\times}x_{2}x_{1}$ and
$x_{2}x_{1}\in{\Bbbk}^{\times}x_{1}x_{2}$ as $R$ is a domain. ∎

######  Lemma 2.3.

[14, Lemma 2.2 & Proposition 2.4] If the point scheme $P$ is not the quadric
$Q$, then $W^{\prime}$ is a five-dimensional subspace of $W$. Moreover, there
exists a normal element in $R_{1}$.

######  Proposition 2.4.

[14, Lemma 2.5] If $\omega\in R_{1}$ is normal and
$\phi\in\operatorname{Aut}(R)$ is defined by $\omega x=x^{\phi}\omega$ for all
$x\in R$, then $\phi\in\Bbbk^{\times}\tau$.

######  Proposition 2.5.

[14, Theorem 2.6] If the point scheme $P$ of $R$ is not the quadric $Q$, then
$\tau\in\operatorname{Aut}(R)$. In this case, $R$ is a Zhang twist of an AS-
regular algebra $R^{\prime}$ that maps onto the (commutative) homogeneous
coordinate ring $S(\mathbb{P}^{3})$. In particular, $R^{\prime}$ contains two
linearly independent central elements of degree one.

###### Proof..

If $P\neq Q$, then $P$ contains a normal element by Lemma 2.3, so by
Proposition 2.4 $\tau\in\operatorname{Aut}(R)$. As a result, one may twist $R$
by $\tau^{-1}$ to obtain an AS-regular algebra $A^{\prime}$ of
$\operatorname{gldim}$ 4 (see, Remark 1.4). Thus, the automorphism
$\tau^{\prime}$ of $Q$ corresponding to $R^{\prime}$ is $\tau\circ\tau^{-1}$,
which is the identity (cf. [10, §1.3]). That is, $R^{\prime}$ maps onto
$S(\mathbb{P}^{3})$.

Now, let $v_{1},v_{2}\in R_{1}$ be linearly independent. By Lemma 2.3, the
span $W^{\prime}$ of defining relations of $R^{\prime}$ contains a five-
dimensional subspace generated by $\\{v_{i}\otimes x-x\otimes v_{i}:x\in
R_{1}^{\prime},i=1,2\\}$, which proves that $v_{1}$ and $v_{2}$, are central.
∎

######  Remark 2.6.

One may characterize any scheme as being reduced or nonreduced, (see e.g., [6,
Example II.9] and [7, Definition §II.3]). We denote the reduced scheme of $P$
by $P_{\mbox{red}}$.

######  Proposition 2.7.

[14, Proposition 2.7] If the point scheme $P$ of $R$ is not the quadric $Q$,
then either

  1. (a)

$P=\mathbb{P}^{3}$

  2. (b)

$P=Q\cup L$ where $L$ is a line in $\mathbb{P}^{3}$ that meets $Q$ in two
points (counted with multiplicity), or

  3. (c)

the reduced scheme $P_{red}$ associated to $P$ is the quadric $Q$ but the
scheme $P$ contains a double line $L$ of (all) multiple points on $P$, where
$L$ corresponds to a line on $Q$ (we denote this situation by $P=Q\uplus L$).

In cases (b) and (c) there is a regular normalizing sequence
$\\{v_{1},v_{2}\\}\subset R_{1}$ such that $L=\mathcal{V}(v_{1},v_{2})$.

######  Proposition 2.8.

Suppose that the point scheme $P$ of $R$ is not $Q$. If
$\sigma|_{Q}=\tau=\operatorname{id}$, then there is a choice of generators
$x_{1},x_{2},x_{3},x_{4}$ for $R$ such that $Q=\mathcal{V}(x_{1}x_{2})$ with
the following six quadratic defining relations.

  1. (a)

$R=S(\mathbb{P}^{3})={\Bbbk}[x_{1},x_{2},x_{3},x_{4}]$ is the polynomial ring
on four variables and $(P,\sigma)=(\mathbb{P}^{3},\operatorname{id})$.

  2. (b)

$R={\Bbbk}[x_{1},x_{2},x_{3},x_{4}]$ with defining relations

$\begin{matrix}x_{3}x_{1}=x_{1}x_{3},&x_{4}x_{2}=x_{2}x_{4},\\\
x_{3}x_{2}=x_{2}x_{3},&x_{4}x_{1}=x_{1}x_{4},\\\
x_{3}x_{4}=x_{4}x_{3},&x_{2}x_{1}=(\alpha-1)x_{1}x_{2},\end{matrix}$

where $\alpha\in{\Bbbk}^{\times}\setminus\\{1,2\\}$. In this case, $P=Q\cup L$
where $L=\mathcal{V}(x_{3},x_{4})$ (so $L$ intersects $Q$ at two distinct
points) and
$\sigma|_{L}(x_{1},x_{2},0,0)=\left((\alpha-1)x_{1},x_{2},0,0\right)$.

  3. (c)

$R={\Bbbk}[x_{1},x_{2},x_{3},x_{4}]$ with defining relations

$\begin{matrix}x_{3}x_{1}=x_{1}x_{3},&x_{2}x_{1}=x_{1}x_{2},\\\
x_{3}x_{2}=x_{2}x_{3},&x_{2}x_{4}-x_{4}x_{2}=x_{1}x_{2},\\\
x_{3}x_{4}=x_{4}x_{3},&x_{1}x_{4}-x_{4}x_{1}=x_{1}x_{2}.\end{matrix}$

In this case, $P=Q\cup L$ where $L=\mathcal{V}(x_{1}-x_{2},x_{3})$ (so $L$
intersects $Q$ at one point with multiplicity two) and
$\sigma|_{L}(x_{1},x_{1},0,x_{4})=\left(x_{1},x_{1},0,x_{1}+x_{4}\right)$.

  4. (d)

$R={\Bbbk}[x_{1},x_{2},x_{3},x_{4}]$ with defining relations

$\begin{matrix}x_{1}x_{2}=x_{2}x_{1},&x_{2}x_{3}=x_{3}x_{2},\\\
x_{1}x_{3}=x_{3}x_{1},&x_{2}x_{4}=x_{4}x_{2},\\\
x_{1}x_{4}=x_{4}x_{1},&x_{3}x_{4}-x_{4}x_{3}=x_{1}x_{2}.\end{matrix}$

In this case, $P=Q\uplus L$ where $L=\mathcal{V}(x_{1},x_{2})\subset Q$ is the
line of intersection of the planes of $Q$ and $\sigma\in\mathrm{Aut}(P)$ is
uniquely determined by its action on the localized homogeneous coordinate
rings of $P$, $S(P)[x_{i}^{-1}]$, as follows: on $S(P)[x_{1}^{-1}]$ and
$S(P)[x_{2}^{-1}]$ we have that $\sigma$ is the identity, but on
$S(P)[x_{3}^{-1}]$ we have

$\sigma(x_{1},x_{2},x_{3},x_{4})=\left(x_{1},x_{2},x_{3},x_{4}-x_{3}^{-1}x_{1}x_{2}\right),$

and on $S(P)[x_{4}^{-1}]$ we have

$\sigma(x_{1},x_{2},x_{3},x_{4})=\left(x_{1},x_{2},x_{3}+x_{4}^{-1}x_{1}x_{2},x_{4}\right).$

  5. (e)

$R={\Bbbk}[x_{1},x_{2},x_{3},x_{4}]$ with defining relations

$\begin{matrix}x_{1}x_{2}=x_{2}x_{1},&x_{2}x_{3}=x_{3}x_{2},\\\
x_{1}x_{3}=x_{3}x_{1},&x_{3}x_{4}=x_{4}x_{3},\\\
x_{1}x_{4}=x_{4}x_{1},&x_{2}x_{4}-x_{4}x_{2}=x_{2}x_{1}.\end{matrix}$

In this case, $P=Q\uplus L$ where
$L=\mathcal{V}(x_{1},x_{3})\subset\mathcal{V}(x_{1})\subset Q$ and
$\sigma\in\mathrm{Aut}(P)$ is uniquely determined by its action on the
localized homogeneous coordinate rings of $P$, $S(P)[x_{i}^{-1}]$, as follows:
on $S(P)[x_{1}^{-1}]$ and $S(P)[x_{3}^{-1}]$ we have that $\sigma$ is the
identity but on $S(P)[x_{2}^{-1}]$ we have

$\sigma(x_{1},x_{2},x_{3},x_{4})=\left(x_{1},x_{2},x_{3},x_{1}+x_{4}\right),$

and on $S(P)[x_{4}^{-1}]$ we have

$\sigma(x_{1},x_{2},x_{3},x_{4})=(x_{1},x_{2}-x_{4}^{-1}x_{2}x_{1},x_{3},x_{4}).$

###### Proof..

Our hypotheses imply that $R$ maps onto the (commutative) homogeneous
coordinate ring, $S(Q)$. As a result, if $x_{1},x_{2},x_{3}$, and $x_{4}$ are
generators for $S(Q)$ such that $Q=\mathcal{V}(x_{1}x_{2})$, then the defining
relations of $R$ must be nonzero linear combinations of $x_{1}x_{2}$ and
$x_{i}x_{j}-x_{j}x_{i}$ for all $i,j$, by 1.2.

  1. (a)

If $P=\mathbb{P}^{3}$, then $\sigma\in\mathrm{Aut}(\mathbb{P}^{3})$ is linear.
Thus, $\sigma=\tau=$ identity and $R=S(\mathbb{P}^{3})$.

  2. (b)

If $L$ is a line in $\mathbb{P}^{3}$ that meets $Q$ in two distinct points,
then we may choose coordinates $x_{1},x_{2},x_{3},x_{4}$ such that
$L=\mathcal{V}(x_{3},x_{4})$ and $Q=\mathcal{V}(x_{1}x_{2})$. By Proposition
2.5, we may choose $x_{3}$ and $x_{4}$ to be central elements in $R$ which
yields five defining relations for $R$. We know that
$x_{1}x_{2}-x_{2}x_{1}\neq 0$ in $R$ as $P\neq\mathbb{P}^{3}$. Thus, $\alpha
x_{1}x_{2}=x_{2}x_{1}-x_{1}x_{2}$ for some $\alpha\in{\Bbbk}^{\times}$. This
yields the sixth defining relation, $x_{2}x_{1}=(\alpha-1)x_{1}x_{2}$. We note
that $\alpha\neq 1$, as $R$ is a domain. However, if
$\alpha\in{\Bbbk}^{\times}\setminus\\{1\\}$, then the algebra is an Ore
extension ${\Bbbk}[x_{1},x_{3},x_{4}][x_{2};\varphi]$ where
$\varphi(x_{1})=(\alpha-1)x_{1}$, $\varphi(x_{3})=x_{3}$ and
$\varphi(x_{4})=x_{4}$ and so, the algebra is regular of global dimension
four. Moreover, the automorphism $\sigma|_{L}$ can be computed by factoring
out the ideal $x_{3}R+x_{4}R$.

  3. (c)

If $L$ is a line in $\mathbb{P}^{3}$ that meets $Q$ in one point counted with
multiplicity two, then we choose coordinates $x_{1},x_{2},x_{3},x_{4}$ such
that $L=\mathcal{V}(x_{1}-x_{2},x_{3})$ and $Q=\mathcal{V}(x_{1}x_{2})$. By
Proposition 2.5, we may choose $x_{1}-x_{2}$ and $x_{3}$ to be central
elements in $R$. This gives seven possible defining relations:
$x_{3}x_{i}=x_{i}x_{3}$, for $i\in\\{1,2,4\\}$, and
$(x_{1}-x_{2})x_{j}=x_{j}(x_{1}-x_{2})$, for $j\in\\{1,2,3,4\\}$. After
eliminating some redundancies in the relations, we have the following four
relations:

$\begin{matrix}x_{1}x_{2}=x_{2}x_{1},&x_{2}x_{3}=x_{3}x_{2}\\\
x_{1}x_{3}=x_{3}x_{1},&x_{3}x_{4}=x_{4}x_{3}\end{matrix}$

By 1.2, $\alpha x_{1}x_{2}=x_{1}x_{4}-x_{4}x_{1}$. For the last relation,
observe that $x_{1}x_{4}-x_{4}x_{1}=x_{2}x_{4}-x_{4}x_{2}$. This yields the
final defining relation of $R$, $\alpha x_{1}x_{2}=x_{2}x_{4}-x_{4}x_{2}$.
Mapping $x_{1}\mapsto\sqrt{\alpha^{-1}}x_{1}$,
$x_{2}\mapsto\sqrt{\alpha^{-1}}x_{2}$, $x_{3}\mapsto x_{3}$,
$x_{4}\mapsto\sqrt{\alpha}x_{4}$ gives the defining relations in (c). This
algebra is the Ore extension
${\Bbbk}[x_{1},x_{2},x_{3}][x_{4};\operatorname{id},\delta]$ where
$\delta(x_{1})=-x_{1}x_{2}$, $\delta(x_{2})=-x_{1}x_{2}$, $\delta(x_{3})=0$;
it may be verified that $\delta$ is a derivation and, hence, that $R$ is
regular. We compute $\sigma|_{L}$ by factoring out the ideal
$(x_{1}-x_{2})R+x_{3}R$.

  4. (d)

If $L$ is the line of intersection of the planes of $Q$, then there exists a
choice of coordinates $x_{1},x_{2},x_{3},x_{4}$ such that
$L=\mathcal{V}(x_{1},x_{2})$ and $Q=\mathcal{V}(x_{1}x_{2})$, and by 2.5, we
may choose $x_{1}$ and $x_{2}$ to be central elements in $R$. Thus, five of
the six defining relations are determined. It can be shown that $\alpha
x_{1}x_{2}=x_{3}x_{4}-x_{4}x_{3}\in{\Bbbk}^{\times}\Omega$ for some
$\alpha\in{\Bbbk}^{\times}$, which gives the final defining relation.
Moreover, $x_{1}\mapsto\sqrt{\alpha^{-1}}x_{1}$,
$x_{2}\mapsto\sqrt{\alpha^{-1}}x_{2}$, $x_{3}\mapsto x_{3}$, $x_{4}\mapsto
x_{4}$ gives the desired defining relations. This algebra is the Ore extension
${\Bbbk}[x_{1},x_{2},x_{3}][x_{4};\operatorname{id},\delta]$ where
$\delta(x_{1})=0$, $\delta(x_{2})=0$, $\delta(x_{3})=-x_{1}x_{2}$ and so, is
regular.

To compute the action of the automorphism, we follow the methods in [10,
Proposition 2.6] and set $Y_{i}^{\prime}=x_{i}\otimes 1$ and
$Z_{i}^{\prime}=1\otimes x_{i}$ for all $i=1,...,4$ in the defining relations
of the algebra. This yields the (commutative) homogeneous coordinate ring $S$
corresponding to the point scheme $P$, $S(P)$, which is isomorphic to the
commutative algebra
${\Bbbk}[Y_{1}^{\prime},Y_{2}^{\prime},Y_{3}^{\prime},Y_{4}^{\prime},Z_{1}^{\prime},Z_{2}^{\prime},Z_{3}^{\prime},Z_{4}^{\prime}]$
with defining relations

$\begin{matrix}Y_{1}^{\prime}Z_{2}^{\prime}=Y_{2}^{\prime}Z_{1}^{\prime},&Y_{2}^{\prime}Z_{3}^{\prime}=Y_{3}^{\prime}Z_{2}^{\prime},\\\
Y_{1}^{\prime}Z_{3}^{\prime}=Y_{3}^{\prime}Z_{1}^{\prime},&Y_{2}^{\prime}Z_{4}^{\prime}=Y_{4}^{\prime}Z_{2}^{\prime},\\\
Y_{1}^{\prime}Z_{4}^{\prime}=Y_{4}^{\prime}Z_{1}^{\prime},&Y_{3}^{\prime}Z_{4}^{\prime}-Y_{4}^{\prime}Z_{3}^{\prime}=Y_{1}^{\prime}Z_{2}^{\prime}.\end{matrix}$

The subalgebra generated by the $Y_{i}^{\prime}$ (respectively, the
$Z_{i}^{\prime}$) is the homogeneous coordinate ring of the left
(respectively, right) projection of $P$ into $\mathbb{P}^{3}$ and is
isomorphic to $S(P)$. For each $S(P)[x_{j}^{-1}]$, set
$Y_{i}=Y_{i}^{\prime}/Y_{j}^{\prime}$ and
$Z_{i}=Z_{i}^{\prime}/Z_{j}^{\prime}$ for all $i\neq j$. On each of these
localizations, $\sigma$ is given by $\sigma(Y_{i})=Z_{i}$.

For $S(P)[x_{j}^{-1}]$ where $j=1,2$, $\sigma$ is the identity. For
$S(P)[x_{3}^{-1}]$, we have $Y_{2}Z_{1}=Y_{1}Z_{2}$, $Y_{4}Z_{1}=Y_{1}Z_{4}$,
$Y_{4}Z_{2}=Y_{2}Z_{4}$, $Z_{1}=Y_{1}$, $Z_{2}=Y_{2}$,
$Z_{4}=Y_{4}+Y_{1}Y_{2}$. For $S(P)[x_{4}^{-1}]$, we have
$Y_{2}Z_{1}=Y_{1}Z_{2}$, $Y_{3}Z_{1}=Y_{1}Z_{3}$, $Y_{3}Z_{2}=Y_{2}Z_{3}$,
$Z_{1}=Y_{1}$, $Z_{2}=Y_{2}$, $Z_{3}=Y_{3}-Y_{1}Y_{2}$. The result follows.

  5. (e)

If $L$ is a line embedded in one of the planes of $Q$, then there exists a
choice of coordinates $x_{1},x_{2},x_{3},x_{4}$ such that
$L=\mathcal{V}(x_{1},x_{3})$ and $Q=\mathcal{V}(x_{1}x_{2})$. By Proposition
2.5, we may choose $x_{1}$ and $x_{3}$ to be central elements in $R$. Thus,
five of the six defining relations are determined and, it can be shown that
$\alpha x_{1}x_{2}=x_{2}x_{4}-x_{4}x_{2}$ for some
$\alpha\in{\Bbbk}^{\times}$, which gives our final defining relation. Mapping
$x_{1}\mapsto\alpha^{-1}x_{1}$, $x_{2}\mapsto x_{2}$, $x_{3}\mapsto x_{3}$,
$x_{4}\mapsto x_{4}$ gives the desired defining relations. This algebra is an
Ore extension ${\Bbbk}[x_{1},x_{2},x_{3}][x_{4};\operatorname{id},\delta]$
where $\delta(x_{1})=0$, $\delta(x_{2})=-x_{2}x_{1}$, $\delta(x_{3})=0$; it
may be verified that $\delta$ is a derivation and, hence, that $R$ is regular.
Moreover, retaining the same notation as above, the algebra $S(P)$ is
isomorphic to the commutative algebra
${\Bbbk}[Y_{1}^{\prime},Y_{2}^{\prime},Y_{3}^{\prime},Y_{4}^{\prime},Z_{1}^{\prime},Z_{2}^{\prime},Z_{3}^{\prime},Z_{4}^{\prime}]$
with defining relations

$\begin{matrix}Y_{1}^{\prime}Z_{2}^{\prime}=Y_{2}^{\prime}Z_{1}^{\prime},&Y_{2}^{\prime}Z_{3}^{\prime}=Y_{3}^{\prime}Z_{2}^{\prime},\\\
Y_{1}^{\prime}Z_{3}^{\prime}=Y_{3}^{\prime}Z_{1}^{\prime},&Y_{3}^{\prime}Z_{4}^{\prime}=Y_{4}^{\prime}Z_{3}^{\prime},\\\
Y_{1}^{\prime}Z_{4}^{\prime}=Y_{4}^{\prime}Z_{1}^{\prime},&Y_{2}^{\prime}Z_{4}^{\prime}-Y_{4}^{\prime}Z_{2}^{\prime}=Y_{2}^{\prime}Z_{1}^{\prime}.\end{matrix}$

For $S(P)[x_{j}^{-1}]$ where $j=1,3$, $\sigma$ is the identity. For
$S(P)[x_{2}^{-1}]$, we have $Y_{3}Z_{1}=Y_{1}Z_{3}$, $Y_{4}Z_{1}=Y_{1}Z_{4}$,
$Y_{4}Z_{3}=Y_{3}Z_{4}$, $Z_{1}=Y_{1}$, $Z_{3}=Y_{3}$, $Z_{4}=Y_{1}+Y_{4}$.
For $S(P)[x_{4}^{-1}]$, we have $Y_{2}Z_{1}=Y_{1}Z_{2}$,
$Y_{3}Z_{1}=Y_{1}Z_{3}$, $Y_{3}Z_{2}=Y_{2}Z_{3}$, $Z_{1}=Y_{1}$,
$Z_{3}=Y_{3}$, $Z_{2}=Y_{2}-Y_{2}Y_{1}$. The result follows.

∎

######  Corollary 2.9.

[14, Corollary 2.13] The map $\tau\in\operatorname{Aut}(P)$ and it commutes
with $\sigma$ on $P$.

######  Proposition 2.10.

The regular algebra $R$ is isomorphic to one of the following algebras if and
only if the point scheme $P$ of $R$ is not the quadric $Q$.

  1. (a)

$R={\Bbbk}[x_{1},x_{2},x_{3},x_{4}]$ with defining relations
$x_{i}^{\tau}x_{j}=x_{j}^{\tau}x_{i}$, for $1\leq i,j\leq 4$ for all
$\tau\in\operatorname{Aut}(\mathbb{P}^{3})$. In this case, $R$ is a twist of
the polynomial ring $S(\mathbb{P}^{3})$ by $\tau$ so
$(P,\sigma)=(\mathbb{P}^{3},\tau)$.

  2. (b)

$R={\Bbbk}[x_{1},x_{2},x_{3},x_{4}]$ with defining relations

$\begin{matrix}x_{3}^{\tau}x_{1}=x_{1}^{\tau}x_{3},&x_{4}^{\tau}x_{2}=x_{2}^{\tau}x_{4},\\\
x_{3}^{\tau}x_{2}=x_{2}^{\tau}x_{3},&x_{4}^{\tau}x_{1}=x_{1}^{\tau}x_{4},\\\
x_{3}^{\tau}x_{4}=x_{4}^{\tau}x_{3},&x_{2}^{\tau}x_{1}=(\alpha-1)x_{1}^{\tau}x_{2},\end{matrix}$

where $\alpha\in{\Bbbk}^{\times}\setminus\\{1,2\\}$ and $\tau$ is given (with
respect to a basis dual to $\\{x_{1},x_{2},x_{3},x_{4}\\}$) by

$\tau\in{\Bbbk}^{\times}\begin{pmatrix}1&0&0&0\\\ 0&t_{22}&0&0\\\
0&0&t_{33}&t_{34}\\\ 0&0&t_{43}&t_{44}\end{pmatrix},$

where $t_{22}\in{\Bbbk}^{\times}$, $t_{ij}\in{\Bbbk}$ for $i,j\in\\{3,4\\}$,
and $t_{33}t_{44}-t_{34}t_{43}\neq 0$. In this case, $P=Q\cup L$ where
$L=\mathcal{V}(x_{3},x_{4})$ (so $L$ intersects $Q$ at two distinct points),
$\sigma|_{Q}=\tau$, and
$\sigma|_{L}(x_{1},x_{2},0,0)=\tau\left((\alpha-1)x_{1},x_{2},0,0\right)$.

  3. (c)

$R={\Bbbk}[x_{1},x_{2},x_{3},x_{4}]$ with defining relations

$\begin{matrix}x_{3}^{\tau}x_{1}=x_{1}^{\tau}x_{3},&x_{2}^{\tau}x_{1}=x_{1}^{\tau}x_{2},\\\
x_{3}^{\tau}x_{2}=x_{2}^{\tau}x_{3},&x_{2}^{\tau}x_{4}-x_{4}^{\tau}x_{2}=x_{1}^{\tau}x_{2},\\\
x_{3}^{\tau}x_{4}=x_{4}^{\tau}x_{3},&x_{1}^{\tau}x_{4}-x_{4}^{\tau}x_{1}=x_{1}^{\tau}x_{2},\end{matrix}$

where $\tau$ is given (with respect to a basis dual to the $x_{i}$) by

$\tau\in{\Bbbk}^{\times}\begin{pmatrix}1&0&0&0\\\ 0&1&0&0\\\
t_{31}&-t_{31}&t_{33}&0\\\ t_{41}&t_{42}&t_{43}&1\end{pmatrix}\text{ or
}\tau\in{\Bbbk}^{\times}\begin{pmatrix}0&1&0&0\\\ 1&0&0&0\\\
t_{31}&-t_{31}&t_{33}&0\\\ t_{41}&t_{42}&t_{43}&1\end{pmatrix},$

where $t_{33}\in{\Bbbk}^{\times}$, $t_{ij}\in{\Bbbk}$. In this case, $P=Q\cup
L$ where $L=\mathcal{V}(x_{1}-x_{2},x_{3})$ (so $L$ intersects $Q$ at one
point with multiplicity two), $\sigma|_{Q}=\tau$, and
$\sigma|_{L}(x_{1},x_{1},0,x_{4})=\tau(x_{1},x_{1},0,x_{1}+x_{4})$.

  4. (d)

$R={\Bbbk}[x_{1},x_{2},x_{3},x_{4}]$ with defining relations

$\begin{matrix}x_{1}^{\tau}x_{2}=x_{2}^{\tau}x_{1},&x_{2}^{\tau}x_{3}=x_{3}^{\tau}x_{2},\\\
x_{1}^{\tau}x_{3}=x_{3}^{\tau}x_{1},&x_{2}^{\tau}x_{4}=x_{4}^{\tau}x_{2},\\\
x_{1}^{\tau}x_{4}=x_{4}^{\tau}x_{1},&x_{3}^{\tau}x_{4}-x_{4}^{\tau}x_{3}=x_{1}^{\tau}x_{2},\end{matrix}$

where $\tau$ is given (with respect to a basis dual to the $x_{i})$ by

$\tau\in{\Bbbk}^{\times}\begin{pmatrix}t_{11}&0&0&0\\\ 0&t_{22}&0&0\\\
t_{31}&t_{32}&t_{33}&t_{34}\\\ t_{41}&t_{42}&t_{43}&t_{44}\end{pmatrix}\text{
or }\tau\in{\Bbbk}^{\times}\begin{pmatrix}0&t_{12}&0&0\\\ t_{21}&0&0&0\\\
t_{31}&t_{32}&t_{33}&t_{34}\\\ t_{41}&t_{42}&t_{43}&t_{44}\end{pmatrix}$

where $t_{ij}\in{\Bbbk}$ and
$t_{12}t_{21}+t_{11}t_{22}=t_{33}t_{44}-t_{34}t_{43}\neq 0$. In this case,
$P=Q\uplus L$ where $L=\mathcal{V}(x_{1},x_{2})\subset Q$ is the line of
intersection the planes of $Q$, $\sigma|_{Q}=\tau$, and
$\sigma\in\mathrm{Aut}(P)$ is uniquely determined by its action on the local
rings $S(P)[x_{i}^{-1}]$, where $S(P)$ is the homogeneous coordinate ring of
$P$ is as follows: on $S(P)[x_{1}^{-1}]$ and $S(P)[x_{2}^{-1}]$ we have that
$\sigma=\tau^{-1}$, but on $S(P)[x_{3}^{-1}]$ we have

$\sigma(x_{1},x_{2},x_{3},x_{4})=\tau^{-1}\left(x_{1},x_{2},x_{3},x_{4}-x_{3}^{-1}x_{1}x_{2}\right),$

and on $S(P)[x_{4}^{-1}]$ we have

$\sigma(x_{1},x_{2},x_{3},x_{4})=\tau^{-1}\left(x_{1},x_{2},x_{3}+x_{4}^{-1}x_{1}x_{2},x_{4}\right).$

  5. (e)

$R={\Bbbk}[x_{1},x_{2},x_{3},x_{4}]$ with defining relations

$\begin{matrix}x_{1}^{\tau}x_{2}=x_{2}^{\tau}x_{1},&x_{2}^{\tau}x_{3}=x_{3}^{\tau}x_{2},\\\
x_{1}^{\tau}x_{3}=x_{3}^{\tau}x_{1},&x_{3}^{\tau}x_{4}=x_{4}^{\tau}x_{3},\\\
x_{1}^{\tau}x_{4}=x_{4}^{\tau}x_{1},&x_{2}^{\tau}x_{4}-x_{4}^{\tau}x_{2}=x_{2}^{\tau}x_{1}.\end{matrix}$

where $\tau$ is given (with respect to a basis dual to the $x_{i})$ by

$\tau\in{\Bbbk}^{\times}\begin{pmatrix}1&0&0&0\\\ 0&t_{22}&0&0\\\
t_{31}&0&t_{33}&0\\\ t_{41}&t_{42}&t_{43}&1\end{pmatrix}$

where $t_{ij}\in{\Bbbk}$ for $i\neq j$ and $t_{22},t_{33}\in{\Bbbk}^{\times}$.
In this case, $P=Q\uplus L$ where
$L=\mathcal{V}(x_{1},x_{3})\subset\mathcal{V}(x_{1})\subset Q$,
$\sigma|_{Q}=\tau$, and $\sigma\in\mathrm{Aut}(P)$ is uniquely determined by
its action on the local rings $S(P)[x_{i}^{-1}]$, where $S(P)$ is the
homogeneous coordinate ring of $P$ is as follows: on $S(P)[x_{1}^{-1}]$ and
$S(P)[x_{3}^{-1}]$ we have that $\sigma=\tau^{-1}$, but on $S(P)[x_{2}^{-1}]$
we have

$\sigma(x_{1},x_{2},x_{3},x_{4})=\tau^{-1}\left(x_{1},x_{2},x_{3},x_{1}+x_{4}\right),$

and on $S(P)[x_{4}^{-1}]$ we have

$\sigma(x_{1},x_{2},x_{3},x_{4})=\tau^{-1}(x_{1},x_{2}-x_{4}^{-1}x_{2}x_{1},x_{3},x_{4}).$

###### Proof..

Using methods similar to [10, Theorem 2.8], we classify the graded degree zero
automorphisms of the algebras listed in Proposition 2.8. Applying Corollary
2.9 to (a), (b) and (c) results in a matrix for $\tau$ that is determined by
the hypotheses that $\tau\in\operatorname{Aut}(Q)\cap\operatorname{Aut}(L)$
and $\tau\mid_{L}\circ\ \sigma\mid_{L}=\sigma\mid_{L}\circ\ \tau\mid_{L}$
(since $\sigma|_{Q}=\operatorname{id}$). The result follows by a computation,
using Wolfram’s Mathematica.

For (d) and (e), we apply $\tau$ to the defining relations of the respective
algebras in Proposition 2.8 rather than working with the commutativity of of
$\tau$ and $\sigma$.

In the case of (d), any element of
$\operatorname{Aut}(Q)\cap\operatorname{Aut}(L)$ may be given (with respect to
a basis dual to the $x_{i}$) by

$\tau\in{\Bbbk}^{\times}\begin{pmatrix}t_{11}&t_{12}&0&0\\\
t_{21}&t_{22}&0&0\\\ t_{31}&t_{32}&t_{33}&t_{34}\\\
t_{41}&t_{42}&t_{43}&t_{44}\end{pmatrix},$

where $t_{ij}\in{\Bbbk}$, $t_{11}t_{21}=t_{12}t_{22}=0$ and
$(t_{12}t_{21}-t_{11}t_{22})(t_{34}t_{43}-t_{33}t_{44})\neq 0$. This matrix
maps the span of the defining relations of the algebra back to itself if and
only if $t_{12}t_{21}+t_{11}t_{22}+t_{34}t_{43}-t_{33}t_{44}=0$, so the result
follows.

In the case of (e), any element of
$\operatorname{Aut}(Q)\cap\operatorname{Aut}(L)$ may be given (with respect to
a basis dual to the $x_{i}$) by

$\tau\in{\Bbbk}^{\times}\begin{pmatrix}t_{11}&0&0&0\\\ 0&t_{22}&0&0\\\
t_{31}&0&t_{33}&0\\\ t_{41}&t_{42}&t_{43}&t_{44}\end{pmatrix},$

where $t_{ij}\in{\Bbbk}$ for $i\neq j$ and $t_{ii}\in{\Bbbk}^{\times}$. This
matrix maps the span of the defining relations of the algebra back to itself
if and only if $t_{11}t_{22}=t_{22}t_{44}$, so the result follows.

∎

##  3\. Regular Algebras whose Point Scheme is the Union of Two Planes

To motivate this section, we begin with an example from [12, Lemma 5.1.1]
where the second author showed that there exist examples of AS-regular
algebras of global dimension four such that their point schemes is exactly a
rank-two quadric.

######  Example 3.1.

[12, Lemma 5.1.1] Consider the $\Bbbk$-algebra $A$ defined by $T(V)/W$ where
$T(V)$ is the tensor algebra, $V$ is the vector space given by $V=\Bbbk
x_{1}\oplus\Bbbk x_{2}\oplus\Bbbk x_{3}\oplus\Bbbk x_{4}$ and $W$ is the ideal
generated by the six relations given below.

$\displaystyle x_{1}x_{2}-x_{2}x_{1},\hskip 11.38109pt$ $\displaystyle
x_{2}x_{3}+x_{3}x_{2},$ $\displaystyle x_{1}x_{3}-x_{3}x_{1},\hskip
11.38109pt$ $\displaystyle x_{2}x_{4}+x_{4}x_{2},$ $\displaystyle
x_{1}x_{4}-x_{4}x_{1},\hskip 11.38109pt$ $\displaystyle
x_{3}x_{4}-x_{4}x_{3}+x_{1}x_{2}.$

The point scheme of $A$ is exactly a rank-two quadric. In fact, Proposition
3.2 below shows that when the point scheme of an algebra, satisfying the
hypotheses of 2.1, is exactly a rank-two quadric, then a normal degree-one
element always exists in $R$.

######  Proposition 3.2.

If the point scheme $P$ of $R$ is $Q$, then there exists generators
$x_{1},\dots,x_{4}$ for $R$ such that $P=Q=\mathcal{V}(x_{1}x_{2})$ and $R$ is
isomorphic to one of the following algebras.

  1. (a)

$R={\Bbbk}[x_{1},x_{2},x_{3},x_{4}]$ with defining relations

$\displaystyle\alpha x_{1}^{\tau}x_{2}=x_{2}^{\tau}x_{1},\hskip 11.38109pt$
$\displaystyle x_{2}^{\tau}x_{3}=x_{3}^{\tau}x_{2},$ $\displaystyle
x_{1}^{\tau}x_{3}=x_{3}^{\tau}x_{1},\hskip 11.38109pt$ $\displaystyle
x_{2}^{\tau}x_{4}=x_{4}^{\tau}x_{2},$ $\displaystyle
x_{1}^{\tau}x_{4}=x_{4}^{\tau}x_{1},\hskip 11.38109pt$ $\displaystyle
x_{3}^{\tau}x_{4}-x_{4}^{\tau}x_{3}=\beta x_{1}^{\tau}x_{2},$

where $\alpha,\beta\in{\Bbbk}^{\times}$ and $\alpha\neq 1$.

  2. (b)

$R={\Bbbk}[x_{1},x_{2},x_{3},x_{4}]$ with defining relations

$\displaystyle x_{1}^{\tau}x_{2}=x_{2}^{\tau}x_{1},\hskip 11.38109pt$
$\displaystyle x_{1}^{\tau}x_{3}=x_{3}^{\tau}x_{1},$ $\displaystyle
x_{2}^{\tau}x_{3}-x_{3}^{\tau}x_{2}=\alpha x_{1}^{\tau}x_{2},\hskip
11.38109pt$ $\displaystyle x_{1}^{\tau}x_{4}-x_{4}^{\tau}x_{1}=\beta
x_{1}^{\tau}x_{2},$ $\displaystyle x_{2}^{\tau}x_{4}=x_{4}^{\tau}x_{2},\hskip
11.38109pt$ $\displaystyle x_{3}^{\tau}x_{4}=x_{4}^{\tau}x_{3},$

where $\alpha,\beta\in{\Bbbk}^{\times}$.

###### Proof..

In this proof, we retain notation used in the proof of 1.5.

  1. (a)

By 1.2, we may choose $x_{1},x_{2},x_{3}$ such that
$x_{1}^{\tau}x_{3}=x_{3}^{\tau}x_{1}$ and
$x_{2}^{\tau}x_{3}=x_{3}^{\tau}x_{2}$ and moreover, we take $\Omega=\delta
x_{1}^{\tau}x_{2}$. Thus, we write $\alpha
x_{1}^{\tau}x_{2}=x_{2}^{\tau}x_{1}$ where $\alpha=1-\alpha_{12}\delta$,
$x_{i}^{\tau}x_{4}-x_{4}^{\tau}x_{i}=\alpha_{i}x_{1}^{\tau}x_{2}$, and
$i\in\\{1,2,3\\}$ with $\alpha_{i}\in{\Bbbk}$.

If $\alpha=1$, this algebra is isomorphic to the algebra
$A={\Bbbk}[y_{1},y_{2},y_{3},y_{4}]$ with defining relations
$y_{1}y_{3}=y_{3}y_{1}$, $y_{2}y_{3}=y_{3}y_{2}$, $y_{1}y_{2}=y_{2}y_{1}$ and
$y_{i}y_{4}-y_{4}y_{i}=\alpha_{i}y_{1}y_{2}$, where $i\in\\{1,2,3\\}$ and
$\alpha_{i}\in{\Bbbk}$. The algebra $A$ is an Ore-extension of a polynomial
ring on three variables given by the automorphism $\sigma(y_{i})=0$, for all
$i$, and the derivation $\gamma(y_{1})=\gamma(y_{2})=0$, $\gamma(y_{3})=-\beta
y_{1}y_{2}$ . If, furthermore, $\alpha_{i}=0$, for all $i$, then $A$ is the
polynomial ring on four generators and $P=\mathbb{P}^{3}$. If $\alpha_{i}\neq
0$ for some $i$, then $\alpha_{i}y_{j}-\alpha_{j}y_{i}$ are central, for
$i,j\in\\{1,2,3\\}$ and so, by 2.7, $Q\subset P$, which contradicts our
hypothesis. Hence, we may assume $\alpha\neq 1$. We rechoose $x_{4}$ such that
$x_{1}^{\tau}x_{4}=x_{4}^{\tau}x_{1}$ and
$x_{2}^{\tau}x_{4}=x_{4}^{\tau}x_{2}$. If, additionally,
$x_{3}^{\tau}x_{4}=x_{4}^{\tau}x_{3}$, then $R$ is a twist of the polynomial
ring and its point scheme is not $Q$. Therefore,
$x_{3}^{\tau}x_{4}-x_{4}^{\tau}x_{3}=\beta x_{1}^{\tau}x_{2}$, for
$\beta\in{\Bbbk}^{\times}$.

  2. (b)

If we choose $x_{1},x_{2},x_{3},x_{4}$ such that
$x_{1}^{\tau}x_{2}=x_{2}^{\tau}x_{1}$, $x_{1}^{\tau}x_{3}=x_{3}^{\tau}x_{1}$,
$x_{2}^{\tau}x_{3}-x_{3}^{\tau}x_{2}=\alpha_{23}x_{1}^{\tau}x_{2}$,
$x_{2}^{\tau}x_{4}=x_{4}^{\tau}x_{2}$, and
$x_{3}^{\tau}x_{4}=x_{4}^{\tau}x_{3}$, where $\alpha_{23}\in{\Bbbk}^{\times}$,
then the sixth relation is of the form
$x_{1}x_{4}-x_{4}x_{1}=\alpha_{14}x_{1}x_{2}$, where $\alpha_{14}\in{\Bbbk}$.
We write these relations as $Mx=0$ where $M$ is a $6\times 4$ matrix and
$x^{T}=(x_{1},x_{2},x_{3},x_{3})$ and obtain the reduced scheme $P_{red}=Q$
where the ideal of $P_{red}$ is given by fifteen polynomials. Now, to
determine the existence of points with multiplicity greater than one, by [7,
Definition §I.5 & Theorems 5.1 & 5.3***While [7, Theorem 5.1] pertains to
affine varieties, we know, using [7, Corollary 2.3], that a projective variety
can be covered by open sets which are then homeomorphic to affine varieties.],
we compute the $1\times 1$ minors of the Jacobian matrix of the fifteen
polynomials of the ideal of $P_{red}$. This yields the possible points of
higher multiplicity.

If $\alpha_{14}\neq 0$, then the $1\times 1$ minors all vanish on
$Q=\mathcal{V}(x_{1},x_{2})$ which implies that points of the form
$(0,0,a,b)\in\mathbb{P}^{3}$ might be of higher multiplicity. Next, we apply
Bertini’s Theorem [7, Theorem 8.18], and intersect $Q$ with a complementary-
dimensional scheme, that is, a 1-dimensional scheme, which is given by the
line $L_{n}=\mathcal{V}(x_{1}-x_{2},nx_{3}-x_{4})$, where
$n\in\mathbb{P}^{1}$. The point of intersection of $L_{n}$ and
$\mathcal{V}(x_{1},x_{2})$ is $(0,0,1,n)$, when $n\in{\Bbbk}$, or $(0,0,0,1)$,
when $n$ is a point at infinity. We determine the vector space dimension of
the localization of the local ring $\mathcal{O}_{Q\cap L_{n}}$ at each of
these points to compute their multiplicities [7]. We obtain a ring isomorphic
to ${\Bbbk}[x]/\langle x^{2}\rangle$ and so, the point has multiplicity two.
This implies that the points on $\mathcal{V}(x_{1},x_{2})$ are multiple points
only as a consequence of being in the intersection of two irreducible
components of $P$, $\mathcal{V}(x_{1})$ and $\mathcal{V}(x_{2})$, explicitly.
Taking $\alpha=\alpha_{23}$ and $\beta=\alpha_{14}$ gives the defining
relations as described. This algebra is an extension of the polynomial ring
${\Bbbk}[x_{2},x_{3},x_{4}]$ by the normal element $x_{1}$ and is thus,
regular.

Otherwise, $\alpha_{14}=0$, and we show that, in this case, we have a
contradiction. Observe that the $1\times 1$ minors of the corresponding
Jacobian matrix vanish on $\mathcal{V}(x_{1},x_{2})$ and on
$\mathcal{V}(x_{1},x_{4})$. Using $L_{n}$ to examine the multiplicity of the
points $\mathcal{V}(x_{1},x_{2})$ as before, we find that all points on
$\mathcal{V}(x_{1},x_{2})$ have multiplicity two (as a consequence of the
intersection of the irreducible components of $P$) except the point
$(0,0,1,0)$, which has multiplicity three. To further analyze the point
$(0,0,1,0)$, consider the points on
$\mathcal{V}(x_{1},x_{4})\setminus\mathcal{V}(x_{1},x_{2})$ that are of the
form $(0,1,n,0)$, where $n\in{\Bbbk}$. In a similar manner as above, we
examine the multiplicity of these points using the line
$K_{n}=\mathcal{V}(x_{3}-nx_{2},x_{1}-x_{4})$. In doing so, we find that the
coordinate ring of $P\cap K_{n}$ is isomorphic to ${\Bbbk}[x]/\langle
x^{2}\rangle$ and so, the points have multiplicity two. This implies that the
point $(0,0,1,0)$ which lies on the line $\mathcal{V}(x_{1},x_{4})$ is a point
on an embedded line in $Q$. Thus, the point scheme of $R$ is
$Q\uplus\mathcal{V}(x_{1},x_{4})$, which contradicts our hypothesis that
$P=Q$.

∎

######  Remark 3.3.

If $P=Q$ and there is a normal element $z\in R_{1}$, then $z$ is also regular
as $R$ is a domain. Moreover, by [2, Theorem 8.16(ii)], the normal element
$z^{\tau}\in R_{1}$ for an automorphism $\tau$ is central in $R^{\tau}$. As a
result, in this case, $R$ is a central extension of an AS-regular of global
dimension three. These central extensions are well-understood algebras (see
e.g., [8]), and by Proposition 3.2, the algebra $R$ will always be such an
algebra.

######  Example 3.4.

The map $\tau$ in Proposition 3.2(a) is given by the automorphism

$\tau\in{\Bbbk}^{\times}\begin{pmatrix}t_{11}&0&0&0\\\ 0&t_{22}&0&0\\\
0&0&t_{33}&t_{34}\\\ 0&0&t_{43}&t_{44}\end{pmatrix},$

where $t_{ij}\in{\Bbbk}$ and $t_{11}t_{22}=t_{33}t_{44}-t_{34}t_{43}\neq 0$.
If $\alpha=-1$, then $\tau$ may also be given by

$\tau\in{\Bbbk}^{\times}\begin{pmatrix}0&t_{12}&0&0\\\ t_{21}&0&0&0\\\
0&0&t_{33}&t_{34}\\\ 0&0&t_{43}&t_{44}\end{pmatrix},$

where $t_{ij}\in{\Bbbk}$ and $t_{12}t_{21}=t_{34}t_{43}-t_{33}t_{44}\neq 0$.

If $\tau\in\operatorname{Aut}(Q)$, then $\tau$ is given by

$\begin{pmatrix}t_{11}&0&0&0\\\ 0&t_{22}&0&0\\\ t_{31}&t_{32}&t_{33}&t_{34}\\\
t_{41}&t_{42}&t_{43}&t_{44}\end{pmatrix}\text{ or
}\begin{pmatrix}0&t_{12}&0&0\\\ t_{21}&0&0&0\\\ t_{31}&t_{32}&t_{33}&t_{34}\\\
t_{41}&t_{42}&t_{43}&t_{44}\end{pmatrix}.$

The first matrix maps the span of the defining relations of $R$ back to itself
if and only if $t_{31}=t_{32}=t_{41}=t_{42}=0$ and
$t_{11}t_{22}+t_{34}t_{43}-t_{33}t_{44}=0$. The second matrix maps the span of
the defining relations of $R$ back to itself if and only if
$(\alpha^{2}-1)t_{12}t_{21}=0$, $t_{31}=t_{32}=t_{41}=t_{42}=0$ and
$t_{12}t_{21}-t_{34}t_{43}+t_{33}t_{44}=0$. Since $\alpha\neq 1$ and
$t_{12}t_{21}\neq 0$ it follows that $\alpha=-1$.

######  Remark 3.5.

The 2-parameter family of algebras obtained in Proposition 3.2 does not
explicitly have the algebra $A$ of Example 3.1 as a member. However, $A$ can
be obtained from the 2-parameter family via the twisting system defined in
[13, Definition 2.1] given by $t_{n}(a_{1}\dots
a_{m})=\Pi_{j=1}^{m}\tau^{1-j-n}t^{n}\tau^{j-1}(a_{j})$ where $m\in\mathbb{N}$
and $a_{j}\in T(V)_{1}$. Take

$t=\begin{pmatrix}a&0&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\ 0&0&0&1\end{pmatrix},\mbox{
and }\hskip 2.84526pt\tau^{-1}=\begin{pmatrix}-q^{-1}&0&0&0\\\ 0&-q&0&0\\\
0&0&-1&0\\\ 0&0&0&1\end{pmatrix},$

to obtain the algebra $A$.

## References

  * [1] M. Artin, J. Tate, and M. Van den Bergh.  Some algebras associated to automorphisms of elliptic curves.  The Grothendieck Festschrift, Vol. I, 86:33–85, 1990.
  * [2] M. Artin, J. Tate, and M. Van den Bergh.  Modules over regular algebras of dimension $3$.  Invent. Math, 106(2):335–388, 1991.
  * [3] M. Artin, J. Tate, and M. Van den Bergh.  Modules over regular algebras of dimension $3$.  Invent. Math., 106(2):335–388, 1991.
  * [4] M. Artin and M. Van den Bergh.  Twisted homogeneous coordinate rings.  J. Algebra, 133(2):249–271, 1990.
  * [5] G. Bellamy, D. Rogalski, T. Schedler, J. T. Stafford, and M. Wemyss.  Noncommutative algebraic geometry, volume 64 of Mathematical Sciences Research Institute Publications.  Cambridge University Press, New York, 2016.  Lecture notes based on courses given at the Summer Graduate School at the Mathematical Sciences Research Institute (MSRI) held in Berkeley, CA, June 2012.
  * [6] D. Eisenbud and J. Harris.  The geometry of schemes, volume 197 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 2000.
  * [7] R. Hartshorne.  Algebraic geometry. Springer-Verlag, New York-Heidelberg, 1977.
  * [8] L. Le Bruyn, S. P. Smith, and M. Van den Bergh.  Central extensions of three-dimensional Artin-Schelter regular algebras.  Math. Z., 222(2):171–212, 1996.
  * [9] T. Levasseur.  Some properties of noncommutative regular graded rings.  Glasgow Math. J., 34(3):277–300, 1992.
  * [10] B. Shelton and M. Vancliff.  Embedding a quantum rank three quadric in a quantum ${\bf P}^{3}$.  Comm. Algebra, 27(6):2877–2904, 1999.
  * [11] S. J. Sierra.  $G$-algebras, twistings, and equivalences of graded categories.  Algebr. Represent. Theory, 14(2):377–390, 2011.
  * [12] H. V. Tran.  Twisting systems and some quantum ${P}^{3}$s with point scheme a rank-2 quadric.  Dissertation, 2022.
  * [13] H.V. Tran and M. Vancliff.  Twisting systems and some quantum ${P}^{3}$s with point scheme a rank-2 quadric.  In K.A. Brown et al, editor, Contemporary Math. Amer. Math. Soc., to appear.
  * [14] M. Vancliff and K. Van Rompay.  Embedding a quantum nonsingular quadric in a quantum ${\bf P}^{3}$.  J. Algebra, 195(1):93–129, 1997.
  * [15] J. J. Zhang.  Twisted graded algebras and equivalences of graded categories.  Proceedings of the London Mathematical Society. Third Series, 72(2):281–311, 1996.