# Stable Surface Regularization for Fast Few-Shot NeRF

Byeongin Joung1, Byeong-Uk Lee2, Jaesung Choe1, Ukcheol Shin3, Minjun Kang1,
Taeyeop Lee1
In So Kweon1, Kuk-Jin Yoon1

KAIST1 KRAFTON2 CMU3

###### Abstract

This paper proposes an algorithm for synthesizing novel views under few-shot
setup. The main concept is to develop a stable surface regularization
technique called Annealing Signed Distance Function (ASDF), which anneals the
surface in a coarse-to-fine manner to accelerate convergence speed. We observe
that the Eikonal loss – which is a widely known geometric regularization –
requires dense training signal to shape different level-sets of SDF, leading
to low-fidelity results under few-shot training. In contrast, the proposed
surface regularization successfully reconstructs scenes and produce high-
fidelity geometry with stable training. Our method is further accelerated by
utilizing grid representation and monocular geometric priors. Finally, the
proposed approach is up to 45 times faster than existing few-shot novel view
synthesis methods, and it produces comparable results in the ScanNet dataset
and NeRF-Real dataset.

##  1 Introduction

Recently, in a way to encode implicit scene appearance and geometry, Neural
Radiance Fields (NeRF) [14] has been introduced. It utilizes Multi Layer
Perceptrons (MLPs) and bulk of training images to obtain radiance and volume
information for each 3D coordinates.

NeRF has shown its effectiveness and potential in retrieving scene geometry,
and was applied to various fields such as novel view synthesis [14], surface
reconstruction [27], dynamic scene rendering [20], and lighting [22]. However,
since NeRF training depends on the amount of images from various viewpoints,
building a neural implicit field with fewer input images is challenging.
Moreover, its nature of scene-by-scene optimization may take over 10 hours,
making it difficult to apply in real-world applications.

Figure 1: Our method can synthesize novel views within 30 minutes by utilizing
multi-level voxel grid optimization. To overcome the limitation of novel view
synthesis with sparse input images, we utilized additional strong geometric
cues and our novel geometric smoothing loss, Annealing SDF loss. Figure 2:
Novel view synthesis comparisons with state-of-the-art works (a) DSNeRF [4]
(b) DDPNeRF [21] (c) voxel grids based approach [24] with eikonal loss [8] and
depth supervision, and (d) ours. Top row: color images, bottom row: depth
maps.

To overcome issues in few-shot setups, series of studies utilized unobserved
viewpoint regularization [18], entropy minimization [9], and geometric priors
[31, 4, 21]. Along with the strategies to handle issues in few-shot setups,
voxel representation [24, 6] and hash encoding [15] present the remarkable
fast training for novel-view synthesis task. However, former approaches
require more than 10 hours for training, while latter still struggle with
sparse input views.

Up to our knowledge, MonoSDF [35] is the first approach to provide analysis on
fast few-shot NeRF training. It studied MLPs and voxel grid optimization using
off-the-shelf geometric cues with the Eikonal loss [8], which is known to be
effective in Signed Distance Function (SDF)-based training. However, their
study revealed that training fast few-shot NeRF with voxel grid optimization
may struggle due to geometrically ambiguous regions driven by sparse input
views.

Similarly, we observe that the naive application of the implicit geometric
regularization, such as the Eikonal loss, fail to extract reliable color and
geometry information in few-shot NeRF setting as visualized in Figure 2-(a, b,
c). Especially, Figure 2-(c) shows that utilizing Eikonal loss in a voxel-
based few-shot environment is not beneficial, as it is difficult to capture
geometric information with sparse inputs and tends to converge to incorrect
local minima. To address this issue, we propose a novel method for stable
surface regularization in fast few-shot setup, called the Annealing Signed
Distance Function (ASDF) loss. This loss enforces strong geometric smoothing
in the early stage of training, thereby enables coarse-to-fine surface
regularization and promote stable convergence. By incorporating the ASDF loss,
our approach shows stable optimization even in challenging conditions for
learning geometry.

By jointly incorporating dense 3D predictions, multi-view consistency and our
ASDF loss, our proposed algorithm successfully synthesize a novel view from
few-shot training, while maintaining fast training time. We show brief
overview in Figure 1.

Our contributions can be summarized as follows:

  * •

Tackle the problem of the Eikonal loss when only a limited number of training
views are available.

  * •

Introduce a novel method to regularize surfaces in fast and few-shot neural
rendering.

  * •

Demonstrates comparable performance with up to 30$\sim$45x faster training
speed.

Figure 3:  The overall pipeline. The proposed architecture utilizes structure
from motion to extract sparse 3D information and camera poses from sparse
input views, while off-the-shelf depth and surface normal are obtained from a
pretrained network [5]. Points are sampled with respect to the camera from the
structure from motion, and the feature value at corresponding points is
extracted. SDF values, gradient of SDF values, and RGB values are decoded by
simple MLP decoder, and RGB, surface normal, and depth values are extracted
along the ray using volumetric rendering. The rendered RGB, depth map, and
surface normal are supervised with their respective label using the loss
functions $L_{C},L_{D}$, and $L_{N}$, while SDF values are supervised with the
loss functions $L_{\text{ASDF}}$ which is composed by $L_{\text{GS}}$, and
$L_{\text{wEik}}$.

##  2 Related Works

Neural Radiance Fields. A newly introduced field, neural implicit
representation [14], has rapidly developed in recent past. In order to enhance
the capabilities of the neural implicit representation, several approaches
have been proposed in recent years. For instance, [30, 2, 17] utilized multi-
view consistency to improve generalization, while [11] proposed an
optimization method based on a bundle of camera poses, which have errors. [29,
34, 36, 19, 7] show that the surface reconstruction can be adapted to neural
implicit representation and help implicit surface representation learning. It
is also adapted to 3D scene reconstruction with neural implicit representation
[1, 27]. To reduce the training time of the optimization, [24, 6] utilized
voxel grids and [15] utilized hash encoding.

Few-shot NeRF. Despite this success, NeRF requires dense inputs for high-
quality novel view synthesis and shows limited performance with sparse inputs.
One of the promising methods to overcome this issue is to use geometric
constraints with NeRF for regularization. RegNeRF [18] introduced patch-based
geometry and color regularization, InfoNeRF [9] proposed ray entropy
minimization and information gain reduction across different viewpoints. While
previous studies, InfoNeRF and RegNeRF, augment the training rays by sampling
unseen neighbor views, our ASDF is designed to learn surface geometry in
coarse-to-fine manner. SinNeRF [33] uses pseudo geometry and color in unseen
view for regularization. More recently, DiffusioNeRF [32] uses a denoising
diffusion model and learns to regularize color and depth within the patch.

NeRF with geometry prior. On the other way, additional constraints are adapted
to NeRF. [12, 16, 31, 28] show geometric priors can be adapted to neural
implicit representation. DONeRF [16] proposed a method that utilizes a
monocular depth oracle network to sample points along the implicit surface to
boost optimization time and enhance performance by reducing redundant
sampling. NerfingMVS [31] also utilized adapted depth priors to sample points
in indoor multi-view stereo (MVS) with structure from motion(SfM). NeuRIS [28]
shows surface normal that can achieve stable optimization in large textureless
regions. SCADE [26] utilized monocular depth estimation while addressing its
inherent ambiguities. Besides on the other works, by utilizing full
information by multi-view consistency and geometric cues from sparse input
views with our strong geometric smoothing loss, we successfully address
limitations of NeRF.

##  3 Preliminary

NeRF [14] is a pioneering paper that encodes appearance and geometry of a
scene within MLPs network to synthesize novel views. Given posed images, the
MLPs are trained to emit color $\mathbf{c}$ and density $\sigma$ at given
query point $\mathbf{p}$ as:

$[\mathbf{c};\sigma]=f(\mathbf{p},\mathbf{d}),$ (1)

where $\mathbf{d}$ is the viewing direction and $f(\cdot)$ indicates the MLPs
network. Then, this paper propose differential volumetric rendering to
synthesize color value as:

$\hat{C}_{r}=\sum_{i=1}^{N}T_{i}\alpha_{i}\mathbf{c}_{i}~{}~{}\text{s.t.}~{}~{}\alpha_{i}=1{-}\exp({-}\sigma_{i}\delta_{i}),$
(2)

where $\hat{C}_{r}$ is the rendered color at the ray $r$, $T_{i}$ is
transmittance defined by
$T_{i}=\text{exp}\left(-\Sigma_{j=1}^{i-1}\sigma_{j}\delta_{j}\right)$ and
$\delta_{i}$ = $t_{i+1}-t_{i}$ is the distance between sampled adjacent query
points.

NeuS [29] proposes a way of 3D reconstruction from differential volumetric
rendering as in Eq. 2. Instead of using density $\sigma$, this paper designs a
unique way of learning SDF as:

$\alpha(\mathbf{p})=\max\left(\frac{-\frac{d\Phi_{s}}{dt}(s(\mathbf{p}))}{\Phi_{s}(s(\mathbf{p}))},0\right),$
(3)

where $\alpha(\mathbf{p})$ is opaqueness at point $\mathbf{p}$. Here,
$\Phi_{s}$ is a sigmoid function and $s(\mathbf{p})$ is the SDF value for the
point $\mathbf{p}$. The surface normal value can be predicted by
differentiating the SDF value with respect to point $\mathbf{p}$:

$n(\mathbf{p})=\frac{\partial s(\mathbf{p})}{\partial{\mathbf{p}}},$ (4)

where $n(\mathbf{p})$ is the surface normal vector at the point $\mathbf{p}$.

##  4 Method

We extract geometric priors for each of the given RGB images using OmniData
[5], and obtain sparse 3D points and camera poses using COLMAP [23]. To
integrate the information provided by these priors, we construct multi-level
feature volume grids and MLP decoders for SDF and color, respectively. We then
use trilinear interpolation to sample the features of query points along
camera rays, and render the results with the MLP decoders. As all of these
processes are differentiable, we can optimize the feature grids and decoders
by supervising them with our loss functions. An overview of our method can be
seen in Figure 3.

Figure 4:  Qualitative results in a real-world scene. It shows that the
Eikonal loss has difficulties in reconstructing surface geometry from a few
training images which results in over-smooth depth and color rendering
qualities. Top : images, bottom : depth maps.

###  4.1 Conventional Surface Regularization Loss

For general implicit neural surface reconstruction tasks with signed distance
functions (SDF) [27, 1, 29, 34, 38], Eikonal loss [8] is commonly used for the
entire neural implicit field to regularize geometry. By utilizing the property
of SDF, the Eikonal loss enforces the gradient of SDF to be a constant value
of 1, as in,

$L_{\text{Eik}}=\sum_{\mathbf{p}\in R}\Big{(}\lVert
n(\mathbf{p})\lVert_{2}-1\Big{)}^{2},$ (5)

where $R$ is a set of rays.

However, Eikonal loss is effective when the nerual implicit representation can
build detailed surface with abundant information from various viewpoints. When
only sparse input views are given, it is difficult to retrieve reliable 3D
geometry because there are many possible convergence points due to ambiguity.
As was mentioned in the introduction section, MonoSDF [35] showed that using
Eikonal loss in few-shot NeRF training encounters unstable optimization during
reconstructing and synthesizing novel views. It is also shown in Figure 4 that
when utilizing voxel grid optimization for fast training in few-shot setup,
using only Eikonal loss brings low-fidelity results of color images and depth
maps.

Therefore, in order to use surface regularization technique in fast few-shot
NeRF training, we should consider a way to give reliable surface supervision,
_i.e_., to build surface-friendly environment. The following question would
be, how can we build surface-friendly environment from sparse input images?

###  4.2 Annealing Signed Distance Function Loss

To remedy this problem, we choose coarse-to-fine strategy in surface
regularization. We propose Annealing Signed Distance Function (ASDF) loss to
do so. Our ASDF loss aims to enforce adaptive geometric smoothing in regard to
the training steps. In the earlier stage of training, ASDF loss guides the
network to learn overall structure, while in the latter stage, the weight of
smoothing loss is decreased so that the network can focus on refining details.
We visualize the overview for ASDF loss in Figure 5.

Our ASDF loss consists of two terms, which are geometric smoothing loss
$L_{\text{GS}}$ and weighted Eikonal loss $L_{\text{Eik}}$. Geometric
smoothing loss, which is the core component of our ASDF loss, is defined as,

$L_{\text{GS}}=\begin{cases}\sum_{\mathbf{p}(t)\in
R^{\prime}}|{s(\mathbf{p}(t))-d(t)}|&b>d(t)\\\ 0&b\leq d(t)\end{cases}.$ (6)

Here, $d(t)$ is $\hat{D}_{r}-t$, which refers to the distance between query
point and the rendered depth value from a given camera ray. Additionally, $b$
is the truncated bound and $R^{\prime}$ is region between surface and moving
truncated bound. Therefore, the geometric smoothing loss enforces SDF value to
be same as the distance between query point and the intersection of the camera
ray and rendered surface. By doing so, the resulted surface from estimated SDF
should be smooth in truncated region.

Figure 5:  The visualization for Annealing SDF loss. The truncated bounds $b$
decrease from $b_{\text{max}}$, camera origin $o$, to $b_{\text{opt}}$ by
following iteration process to capture detailed geometry by reducing smoothing
area. $L_{\text{GS}}$ is applied to $\textbf{p}(t)$ within grey region
$R^{\prime}$.

To enable coarse-to-fine strategy, we adjust the bound $b$ during the
optimization process. $b$ decreases from $b_{\text{max}}$ to $b_{\text{opt}}$
as the training iteration increases, as in,

$b=\begin{cases}\frac{i_{\text{opt}}-i}{i_{\text{opt}}}(b_{\text{max}}-b_{\text{opt}})+b_{\text{opt}}&i\leq
i_{\text{opt}}\\\ b_{\text{opt}}&i>i_{\text{opt}}\end{cases}.$ (7)

These equations make geometric smoothing in wider range of query points in the
early training stage, and reduce this range gradually, so that the network
first optimizes to coarse surface, and then progressively recover detailed
geometry.

The second term, weighted Eikonal loss, is defined as was introduced in [27],

$L_{\text{wEik}}=\frac{1}{\sum_{\mathbf{p}\in
R}|s(\mathbf{p})|}\sum_{\mathbf{p}\in R}\Big{(}(\lVert
n(\mathbf{p})\lVert_{2}-1)^{2}\cdot|s(\mathbf{p})|\Big{)}.$ (8)

Thus, our annealing signed distance function (ASDF) is represented as
$L_{\text{ASDF}}=L_{\text{GS}}+\lambda_{\text{wEik}}L_{\text{wEik}}$.

###  4.3 Architecture

Our architecture consists of multi-level feature grids $V_{s}^{i}$ for SDF and
$V_{c}^{i}$ for color, as well as MLP decoders $f_{s}$ and $f_{c}$ for SDF and
color, respectively. Features are extracted from each feature volume grid by
interpolating the nearest 8 points to normalized sampled query points. These
extracted features are concatenated and fed into each decoder $f_{s}$ and
$f_{c}$ with positional encoding [25] to obtain the SDF value $s$ and color
value $c$ at the query point $p$, as in,

$s(\mathbf{p})=f_{s}\big{(}\text{interp}(\mathbf{p},V_{s}^{i}),\text{PE}(\mathbf{p})\big{)},$
(9)
$c(\mathbf{p})=f_{c}\big{(}\text{interp}(\mathbf{p},V_{c}^{i}),\text{PE}(\mathbf{p})\big{)},$
(10)

where $\text{interp}(\cdot)$ is trilinear interpolation and $\text{PE}(\cdot)$
indicates positional encoding [14].

To optimize our network, we employed three rendering losses for each rendered
value, as well as aforementioned ASDF loss. The rendering losses for rendered
color and rendered normal are based on the Euclidean distance between the
ground truth and predicted values:

$L_{C}=\sum_{r\in R}\lVert
C_{r}-\hat{C}_{r}\lVert_{2},~{}~{}~{}L_{N}=\sum_{r\in R}\lVert
N_{r}-\hat{N}_{r}\lVert_{2}.$ (11)

$C_{r}$ refers to ground truth color and $N_{r}$ and $\hat{N}_{r}$ are surface
normal predicted by OmniData and rendered surface normal, respectively.

For dense depth prediction, [35] use ground truth depth information to scale
initial off-the-shelf depth estimation results. In contrast, we do not utilize
ground truth, therefore applied a least squares optimization to directly scale
it to the projected sparse points from SfM, using a scale factor $w$ and a
shift factor $b$. To supervise the scaling, we used rendered depth in the
following loss function:

$L_{D}=\begin{cases}\sum_{r\in
R}\lVert(wD_{r}+b)-\hat{D_{r}}\lVert_{2}&N_{s}>0\\\
0&\text{otherwise}\end{cases},$ (12)

where $D_{r}$ is a predicted depth by OmniData. $N_{s}$ is the number of
projected sparse points to the camera. Note that since some images may not
contain any projected sparse points, $w$ and $b$ cannot be solved and are
therefore not supervised with depth. The total loss for optimization for our
architecture is given by:

$L_{total}=L_{C}+\lambda_{N}L_{N}+\lambda_{D}L_{D}+\lambda_{\text{ASDF}}L_{\text{ASDF}}.$
(13)

##  5 Experiments

Figure 6:  Analysis on geometric regularization loss. For both the Eikonal
loss (blue) and our loss function (orange), we plotted the mean (a) and
standard deviation (b) for the gradient at the nearby surface ($<$ 10cm) and
far from the surface (90cm $\sim$ 1m) against iterations with ideal value
(red). In addition, we provided visualizations of the rendered RGB and depth
maps for both cases in (c). The left images show the rendered results
supervised only by the Eikonal loss for the SDF loss, while the middle images
are supervised by our annealing SDF loss. The last column shows the ground
truth images. In (c), top row : color images, bottom row : depth maps.

###  5.1 Implementation Details

We implemented our system using a single TITAN RTX 24GB and adjusted the voxel
sizes for each scene to fit the GPU memory and improve performance. We
utilized $i=4$ for both SDF feature grids and color feature grids in multi-
resolution feature grids. Our decoders, $f_{c}$, and $f_{s}$, were implemented
using MLPs with a single layer containing 128 channels. The learning rates for
the decoder and feature grids were set to 0.001 and 0.01, respectively. For
the initial value of standard deviation for the surface reconstruction
parameter, we used 0.3 and a learning rate of 0.001, similar to [29]. We used
the Adam optimizer [10] to optimize our system. To optimize our network, we
set the following values for [$\lambda_{N}$, $\lambda_{D}$,
$\lambda_{\text{ASDF}}$, $\lambda_{\text{wEik}}$, $i_{opt}$]: [0.1, 0.12, 0.2,
0.75, 150]. The truncated bounds [$b_{\text{max}}$, $b_{\text{opt}}$] were
dependent on the scene scale. Since PyTorch does not support differentiable
grid sampling, we employ a customized grid sampler [27].

###  5.2 Dataset and Few-Shot Training Scheme

The ScanNet dataset [3] consists of RGB-D Sequences in indoor environments and
contains over 2.5 million images from more than 1000 real-world indoor scans.
We selected five scenes from the ScanNet dataset and used 18 to 20 images from
each pair of scenes that share common surfaces for training, as well as 8
images for validation and testing, following the protocol used in [21]. We did
not use dense measurements from the sensor, but rather relied on the results
of SfM and deep dense priors to match scale. The NeRF-Real dataset [13, 14]
includes eight forward-facing scenes. For each scene, we accessed 2 views, 5
views and 10 views to train our network. We followed the official protocol to
evaluate the performance of our method on the NeRF-Real dataset [4].

###  5.3 Impact of utilizing ASDF Loss

Stable optimization. In Figure 6-(a,b), while the mean and standard deviation
for the Eikonal loss shows unstable, ours shows stable optimization process.
By supporting geometric smoothing effect from ASDF loss, our approach
dramatically decrease the instability of initial optimization process with the
Eikonal loss. Also, we observed that unstable training affects the qualitative
results. As shown in Figure 6-(c), using only Eikonal loss results in
unreliable color and depth rendering. Thanks to our geometric smoothing term,
our approach help network be able to make clear color image and geometry.

Figure 7:  Analysis on two geometric regularizations in terms of number of
training images. (a) We plot the relationship between the number of training
images and the rendered image quality using PSNR ($\uparrow$) metric. (b)
sampled rendering results with ground truth images. Note that $\\#$91 (top
row) indicate the results using 91 images and similarly for $\\#$25 (bottom
row).

Few-shot learning. We examined the relationship between the number of training
images and the performance for novel view synthesis using our training scheme.

We used PSNR to measure performance. As shown in Figure 7-(a), due to the
smoothing effect of our proposed method, our performance was slightly lower
than the naive approach when a lot of images are used for training. However,
we observed a significant performance drop at certain number of images with
the Eikonal loss, whereas our approach exhibited a stable performance
decrease. In the qualitative results presented in Figure 7-(b), the upper row
depicts novel view synthesis with 91 training images, and the lower row shows
synthesis with 25 training images. Despite the reduced number of images, our
approach showed no significant difference in visualization. In contrast, the
naive approach failed to synthesize reliable novel view.

###  5.4 Comparison with State-of-the-Arts

Baselines and metrics. We compared our method with baseline approaches for
novel view synthesis, namely NeRF [14] and state-of-the-art few-shot NeRF with
SfM: DS-NeRF [4], DDP-NeRF [21] and SCADE [26]. DS-NeRF utilized naive results
of SfM and used the error as weight for supervision. DDP-NeRF utilized SfM to
predict dense depth maps and uncertainty. SCADE exploited ambiguity-aware
depth estimates to address inherent ambiguities of monocular depth estimation
in-the-wild indoor scenes.

To evaluate the quality of the rendered images, we employed three color
evaluation metrics: PSNR, SSIM, and LPIPS, as well as a single geometric
evaluation metric for rendered depth, RMSE error, as following [21]. PSNR
measures the color difference between two images, indicating the overall
quality of the images. In contrast, SSIM is used to evaluate structural
similarity between two images. Both evaluation metrics lack perception loss,
which was addressed by [37] through the introduction of LPIPS, a metric that
passes images to a pre-trained network and measures the difference between
feature maps.

Figure 8: Qualitative comparison in the ScanNet dataset [3]. We utilized
official PyTorch Implementations for DSNeRF [4], DDPNeRF [21] and SCADE [26].
In contrast to alternative methods, our approach exhibits greater robustness
on planar surfaces such as drawers and floors.

| Time $\downarrow$ | PSNR $\uparrow$ | SSIM $\uparrow$ | LPIPS $\downarrow$ | RMSE $\downarrow$
---|---|---|---|---|---
NeRF | 23h | 19.03 | 0.670 | 0.398 | 1.163
DS-NeRF | 22h | 20.85 | 0.713 | 0.344 | 0.447
DDPNeRF | 15h | 20.96 | 0.737 | 0.294 | 0.236
SCADE | 13h | 21.54 | 0.732 | 0.292 | 0.253
Ours w/o ASDF | 0.5h | 20.52 | 0.633 | 0.408 | 0.307
Ours | 0.5h | 21.57 | 0.720 | 0.292 | 0.228
|  |  |  |  |

Table 1: Quantitative comparison in the ScanNet dataset [3]. Ours demonstrates
plausible performance with a significantly improved optimization time. To
compute the RMSE error of SCADE [26], we employed the official PyTorch
implementation.

ScanNet dataset. We evaluated our method on ScanNet (Figure 8) with NeRF [14],
DSNeRF [4], DDPNeRF [21], SCADE [26] and Ours without ASDF loss, which is
utilizing Eikonal loss. We selected three scenes and visualized the rendered
color images. The visualization results illustrated in Figure 8 show that our
approach is more robust in homogeneous regions, such as a chair or floor.

For quantitative evaluation, we used the same scene as [21]. According to the
results presented in Table 1, our approach shows promising performance in most
metrics compared to the previous state-of-the-arts. Note that while
maintaining comparable results, ours accomplished a speed boost of 30 times
compared to DDPNeRF [21], and up to 45 times compared to NeRF [14].

NeRF-Real dataset. To show our ability in limited viewing direction scenes, we
evaluated our method on the NeRF-Real dataset with NeRF [14] and DSNeRF [4]
(Figure 10). We used every 8-th image for testing and trained with 2 views
following [4]. Ours shows plausible visualization results when compared to
another approaches.

For quantitative result in NeRF-Real dataset, we evaluate our approach with
the average value for PSNR, SSIM and LPIPS of 2 views, 5 views and 10 views
data split, following that of DSNeRF [4]. Results are shown in Table 3.

Similar to the results from ScanNet dataset, our method outperforms vanilla
NeRF in the most of the metrics in every scenes. Compared to DSNeRF, our
approach shows comparable results on PSNR and SSIM metrics. Please note that
in LPIPS metric, ours dramatically outperforms both NeRF and DSNeRF. From this
observation, we believe that our proposed fast few-shot NeRF training scheme
enables reliable radiance optimization that is sufficient to feature
retrieval, with up to x45 training time.

Figure 9:  Ablation study for geometry priors with our geometric smoothing
loss. Top: rendered color images, mid: rendered depth maps, bottom: rendered
surface normal maps.

Preserve (✓) | Evaluation
---|---
RGB | Depth | Normal | PSNR $\uparrow$ | SSIM $\uparrow$ | LPIPS $\downarrow$ | RMSE $\downarrow$
✓ |  |  | 16.88 | 0.501 | 0.477 | 1.693
✓ | ✓ |  | 21.07 | 0.704 | 0.307 | 0.239
✓ | ✓ | ✓ | 21.17 | 0.708 | 0.303 | 0.228
|  |  |  |  |  |

Table 2: Ablation study for dense predictions with our ASDF loss. Figure 10:
Qualitative comparison in NeRF-Real dataset [13, 14]. Ours demonstrates
plausible results, in contrast with other methods that exhibit blurry effects
or unstable shapes, such as TVs and handrails.

|  | NeRF (Time: 23h) |  |  | DSNeRF (Time: 22h) |  |  | Ours w/o ASDF (Time: 0.5h) |  |  |  Ours (Time: 0.5h) |
---|---|---|---|---|---|---|---|---|---|---|---|---
| PSNR $\uparrow$ | SSIM $\uparrow$ | LPIPS $\downarrow$ | PSNR $\uparrow$ | SSIM $\uparrow$ | LPIPS $\downarrow$ | PSNR $\uparrow$ | SSIM $\uparrow$ | LPIPS $\downarrow$ | PSNR $\uparrow$ | SSIM $\uparrow$ | LPIPS $\downarrow$
fern | 20.00 | 0.58 | 0.41 | 20.60 | 0.60 | 0.43 | 20.19 | 0.51 | 0.43 | 20.26 | 0.56 | 0.34
flower | 17.79 | 0.49 | 0.43 | 21.79 | 0.62 | 0.35 | 19.87 | 0.54 | 0.31 | 19.27 | 0.51 | 0.29
fortress | 19.13 | 0.55 | 0.53 | 23.85 | 0.66 | 0.35 | 22.93 | 0.66 | 0.21 | 24.08 | 0.67 | 0.18
horns | 17.57 | 0.51 | 0.50 | 18.86 | 0.53 | 0.54 | 18.13 | 0.47 | 0.44 | 17.85 | 0.50 | 0.39
leaves | 13.73 | 0.26 | 0.52 | 15.93 | 0.35 | 0.5 | 16.90 | 0.48 | 0.33 | 16.54 | 0.45 | 0.32
orchids | 14.79 | 0.34 | 0.45 | 16.15 | 0.39 | 0.44 | 16.16 | 0.37 | 0.39 | 15.84 | 0.42 | 0.27
room | 22.23 | 0.78 | 0.32 | 24.46 | 0.86 | 0.19 | 22.22 | 0.74 | 0.28 | 23.22 | 0.81 | 0.20
trex | 18.34 | 0.63 | 0.34 | 18.82 | 0.63 | 0.39 | 19.04 | 0.56 | 0.39 | 19.07 | 0.59 | 0.30
Avg. | 17.95 | 0.52 | 0.42 | 20.06 | 0.58 | 0.40 | 19.43 | 0.54 | 0.35 | 19.51 | 0.56 | 0.29
|  |  |  |  |  |  |  |  |  |  |  |

Table 3: Quantitative comparison in NeRF-Real Dataset [13, 14]. The results
are the average of 2 views, 5 views, and 10 views following DSNeRF [4].

###  5.5 Ablation Study

Utilization of deep dense priors. In order to evaluate the effectiveness of
deep dense priors which are utilized in our approach, we ablate a few variants
that employ different types and numbers of 3D modalities with our ASDF loss.

The task of producing accurate dense predictions with RGB images only is
challenging, as demonstrated in Figure 9. However, with the incorporation of
deep dense priors with supervision, we observed a significant improvement in
all metrics, as indicated in Table 2.

##  6 Conclusion

We have presented a fast few-shot NeRF with deep dense priors and structure
from motion. Given the difficulty of optimizing geometric information from a
few views in complex scenes, we propose a new surface regularization loss,
Annealing Signed Distance Function loss, that enforces geometric smoothing and
improves the performance for synthesizing novel view. As a result, we have
successfully connected deep dense priors, multi-view consistency and multi-
resolution voxel grids for novel view synthesis with sparse input views.

Our method can be further enhanced by adapting recent approaches such as [15,
6] to improve the optimization speed of the NeRF. Also, uncertainty handling
for geometric priors may boost the performance by reducing the error of off-
the-shelf network.

For the limitation of this method, we think that our Annealing Signed Distance
Function requires hyper-parameters that are dependent on the scene geometry or
SfM results, _e.g_., accuracy of camera poses. We think that solving this
issue in an adaptive manner without heuristic tuning can be a future
direction.

Acknowledgements This work was supported by the National Research Foundation
of Korea (NRF) grant funded by the Korea government (MSIT)
(NRF2022R1A2B5B03002636).

## References

  * Azinović et al. [2022] Dejan Azinović, Ricardo Martin-Brualla, Dan B Goldman, Matthias Nießner, and Justus Thies.  Neural rgb-d surface reconstruction.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 6290–6301, 2022.
  * Chen et al. [2021] Anpei Chen, Zexiang Xu, Fuqiang Zhao, Xiaoshuai Zhang, Fanbo Xiang, Jingyi Yu, and Hao Su.  Mvsnerf: Fast generalizable radiance field reconstruction from multi-view stereo.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 14124–14133, 2021.
  * Dai et al. [2017] Angela Dai, Angel X Chang, Manolis Savva, Maciej Halber, Thomas Funkhouser, and Matthias Nießner.  Scannet: Richly-annotated 3d reconstructions of indoor scenes.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 5828–5839, 2017.
  * Deng et al. [2022] Kangle Deng, Andrew Liu, Jun-Yan Zhu, and Deva Ramanan.  Depth-supervised nerf: Fewer views and faster training for free.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 12882–12891, 2022.
  * Eftekhar et al. [2021] Ainaz Eftekhar, Alexander Sax, Jitendra Malik, and Amir Zamir.  Omnidata: A scalable pipeline for making multi-task mid-level vision datasets from 3d scans.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 10786–10796, 2021.
  * Fridovich-Keil et al. [2022] Sara Fridovich-Keil, Alex Yu, Matthew Tancik, Qinhong Chen, Benjamin Recht, and Angjoo Kanazawa.  Plenoxels: Radiance fields without neural networks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 5501–5510, 2022.
  * Fu et al. [2022] Qiancheng Fu, Qingshan Xu, Yew-Soon Ong, and Wenbing Tao.  Geo-neus: Geometry-consistent neural implicit surfaces learning for multi-view reconstruction.  _arXiv preprint arXiv:2205.15848_ , 2022.
  * Gropp et al. [2020] Amos Gropp, Lior Yariv, Niv Haim, Matan Atzmon, and Yaron Lipman.  Implicit geometric regularization for learning shapes.  _arXiv preprint arXiv:2002.10099_ , 2020.
  * Kim et al. [2022] Mijeong Kim, Seonguk Seo, and Bohyung Han.  Infonerf: Ray entropy minimization for few-shot neural volume rendering.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 12912–12921, 2022.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Lin et al. [2021] Chen-Hsuan Lin, Wei-Chiu Ma, Antonio Torralba, and Simon Lucey.  Barf: Bundle-adjusting neural radiance fields.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 5741–5751, 2021.
  * Liu et al. [2020] Lingjie Liu, Jiatao Gu, Kyaw Zaw Lin, Tat-Seng Chua, and Christian Theobalt.  Neural sparse voxel fields.  _Advances in Neural Information Processing Systems_ , 33:15651–15663, 2020.
  * Mildenhall et al. [2019] Ben Mildenhall, Pratul P Srinivasan, Rodrigo Ortiz-Cayon, Nima Khademi Kalantari, Ravi Ramamoorthi, Ren Ng, and Abhishek Kar.  Local light field fusion: Practical view synthesis with prescriptive sampling guidelines.  _ACM Transactions on Graphics (TOG)_ , 38(4):1–14, 2019.
  * Mildenhall et al. [2021] Ben Mildenhall, Pratul P Srinivasan, Matthew Tancik, Jonathan T Barron, Ravi Ramamoorthi, and Ren Ng.  Nerf: Representing scenes as neural radiance fields for view synthesis.  _Communications of the ACM_ , 65(1):99–106, 2021.
  * Müller et al. [2022] Thomas Müller, Alex Evans, Christoph Schied, and Alexander Keller.  Instant neural graphics primitives with a multiresolution hash encoding.  _ACM Trans. Graph._ , 41(4):102:1–102:15, 2022.
  * Neff et al. [2021] Thomas Neff, Pascal Stadlbauer, Mathias Parger, Andreas Kurz, Joerg H Mueller, Chakravarty R Alla Chaitanya, Anton Kaplanyan, and Markus Steinberger.  Donerf: Towards real-time rendering of compact neural radiance fields using depth oracle networks.  In _Computer Graphics Forum_ , pages 45–59. Wiley Online Library, 2021.
  * Nguyen-Ha et al. [2022] Phong Nguyen-Ha, Lam Huynh, Esa Rahtu, Jiri Matas, and Janne Heikkila.  Hrf-net: Holistic radiance fields from sparse inputs.  _arXiv preprint arXiv:2208.04717_ , 2022.
  * Niemeyer et al. [2022] Michael Niemeyer, Jonathan T Barron, Ben Mildenhall, Mehdi SM Sajjadi, Andreas Geiger, and Noha Radwan.  Regnerf: Regularizing neural radiance fields for view synthesis from sparse inputs.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 5480–5490, 2022.
  * Oechsle et al. [2021] Michael Oechsle, Songyou Peng, and Andreas Geiger.  Unisurf: Unifying neural implicit surfaces and radiance fields for multi-view reconstruction.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 5589–5599, 2021.
  * Pumarola et al. [2021] Albert Pumarola, Enric Corona, Gerard Pons-Moll, and Francesc Moreno-Noguer.  D-nerf: Neural radiance fields for dynamic scenes.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 10318–10327, 2021.
  * Roessle et al. [2022] Barbara Roessle, Jonathan T Barron, Ben Mildenhall, Pratul P Srinivasan, and Matthias Nießner.  Dense depth priors for neural radiance fields from sparse input views.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 12892–12901, 2022.
  * Rudnev et al. [2022] Viktor Rudnev, Mohamed Elgharib, William Smith, Lingjie Liu, Vladislav Golyanik, and Christian Theobalt.  Nerf for outdoor scene relighting.  In _Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XVI_ , pages 615–631. Springer, 2022.
  * Schonberger and Frahm [2016] Johannes L Schonberger and Jan-Michael Frahm.  Structure-from-motion revisited.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 4104–4113, 2016.
  * Sun et al. [2022] Cheng Sun, Min Sun, and Hwann-Tzong Chen.  Direct voxel grid optimization: Super-fast convergence for radiance fields reconstruction.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 5459–5469, 2022.
  * Tancik et al. [2020] Matthew Tancik, Pratul Srinivasan, Ben Mildenhall, Sara Fridovich-Keil, Nithin Raghavan, Utkarsh Singhal, Ravi Ramamoorthi, Jonathan Barron, and Ren Ng.  Fourier features let networks learn high frequency functions in low dimensional domains.  _Advances in Neural Information Processing Systems_ , 33:7537–7547, 2020.
  * Uy et al. [2023] Mikaela Angelina Uy, Ricardo Martin-Brualla, Leonidas Guibas, and Ke Li.  Scade: Nerfs from space carving with ambiguity-aware depth estimates.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 16518–16527, 2023.
  * Wang et al. [2022a] Jingwen Wang, Tymoteusz Bleja, and Lourdes Agapito.  Go-surf: Neural feature grid optimization for fast, high-fidelity rgb-d surface reconstruction.  _arXiv preprint arXiv:2206.14735_ , 2022a.
  * Wang et al. [2022b] Jiepeng Wang, Peng Wang, Xiaoxiao Long, Christian Theobalt, Taku Komura, Lingjie Liu, and Wenping Wang.  Neuris: Neural reconstruction of indoor scenes using normal priors.  _arXiv preprint arXiv:2206.13597_ , 2022b.
  * Wang et al. [2021a] Peng Wang, Lingjie Liu, Yuan Liu, Christian Theobalt, Taku Komura, and Wenping Wang.  Neus: Learning neural implicit surfaces by volume rendering for multi-view reconstruction.  _arXiv preprint arXiv:2106.10689_ , 2021a.
  * Wang et al. [2021b] Qianqian Wang, Zhicheng Wang, Kyle Genova, Pratul P Srinivasan, Howard Zhou, Jonathan T Barron, Ricardo Martin-Brualla, Noah Snavely, and Thomas Funkhouser.  Ibrnet: Learning multi-view image-based rendering.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 4690–4699, 2021b.
  * Wei et al. [2021] Yi Wei, Shaohui Liu, Yongming Rao, Wang Zhao, Jiwen Lu, and Jie Zhou.  Nerfingmvs: Guided optimization of neural radiance fields for indoor multi-view stereo.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 5610–5619, 2021.
  * Wynn and Turmukhambetov [2023] Jamie Wynn and Daniyar Turmukhambetov.  Diffusionerf: Regularizing neural radiance fields with denoising diffusion models.  _arXiv preprint arXiv:2302.12231_ , 2023.
  * Xu et al. [2022] Dejia Xu, Yifan Jiang, Peihao Wang, Zhiwen Fan, Humphrey Shi, and Zhangyang Wang.  Sinnerf: Training neural radiance fields on complex scenes from a single image.  In _Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XXII_ , pages 736–753. Springer, 2022.
  * Yariv et al. [2021] Lior Yariv, Jiatao Gu, Yoni Kasten, and Yaron Lipman.  Volume rendering of neural implicit surfaces.  _Advances in Neural Information Processing Systems_ , 34:4805–4815, 2021.
  * Yu et al. [2022] Zehao Yu, Songyou Peng, Michael Niemeyer, Torsten Sattler, and Andreas Geiger.  Monosdf: Exploring monocular geometric cues for neural implicit surface reconstruction.  _arXiv preprint arXiv:2206.00665_ , 2022.
  * Zhang et al. [2021] Jingyang Zhang, Yao Yao, and Long Quan.  Learning signed distance field for multi-view surface reconstruction.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 6525–6534, 2021.
  * Zhang et al. [2018] Richard Zhang, Phillip Isola, Alexei A Efros, Eli Shechtman, and Oliver Wang.  The unreasonable effectiveness of deep features as a perceptual metric.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 586–595, 2018.
  * Zhu et al. [2023] Zihan Zhu, Songyou Peng, Viktor Larsson, Zhaopeng Cui, Martin R Oswald, Andreas Geiger, and Marc Pollefeys.  Nicer-slam: Neural implicit scene encoding for rgb slam.  _arXiv preprint arXiv:2302.03594_ , 2023.


# On the Largest intersecting set in the general linear group and its
subgroups

Milad Ahanjideh  Department of Industrial Engineering, Boğaziçi University,
Turkey<EMAIL_ADDRESS>
###### Abstract.

Let $q$ be a power of a prime number and $V$ be the $2$-dimensional column
vector space over a finite field $\mathbb{F}_{q}$. Assume that
$SL_{2}(V)<G\leq GL_{2}(V)$. In this paper we prove an Erdős-Ko-Rado theorem
for intersecting sets of G. We show that every maximum intersecting set of $G$
is either a coset of the stabilizer of a point or a coset of $H_{\langle
w\rangle}$, where $H_{\langle w\rangle}=\\{M\in G:\forall v\in
V,Mv-v\in\langle w\rangle\\}.$ It is also shown that every intersecting set of
$G$ is contained in a maximum intersecting set.

###### Key words and phrases:

Erdős-Ko-Rado property, the general linear group

###### 2010 Mathematics Subject Classification:

05D05, 20B35

##  1\. Introduction

In 1961, Erdős, Ko and Rado obtained the size of the largest family of subsets
of size $r$ from $\\{1,\ldots,n\\}$ such that any two of these subsets have a
nonempty intersection. The famous Erdős-Ko-Rado theorem [4] states that if
$n\geq 2r$, then the largest family has size ${n-1\choose r-1}$, and for
$n>2r$, the only families that have this size are the families of all subsets
containing a fixed element from $\\{1,\ldots,n\\}$. Many analogous results
have been proved for other mathematical objects. In this paper, we consider
the Erdős-Ko-Rado theorem for the linear groups.

Let $\Omega$ be a finite set and $K$ a permutation group on it. We say that a
subset $A$ of $K$ is intersecting if for any $\delta,\tau\in A$, there exists
$x\in\Omega$ such that $\delta(x)=\tau(x)$. It is obvious that the stabilizer
of a point is an intersecting set. If the size of every intersecting set of a
group $G$ is at most the size of the largest stabilizer of a point, we say $G$
has the EKR property while $G$ has the strict EKR property if every maximum
intersecting set is a coset of a stabilizer of a point.

Let $S_{n}$ denote the symmetric group of degree $n$. In 1977, Frankl and Deza
[5] proved that $S_{n}$ has the EKR property. After that, Cameron and Ku [3]
showed that $S_{n}$ has the strict EKR property as well which answered
affirmatively to the conjecture posed in [5].

It is worth mentioning that group action plays an essential role to determine
which groups have (strict) EKR property. Because a group can have the EKR
property under an action while it does not have the same property under the
other action. We refer the reader to see [2] for finding an example of such
these groups.

A natural question that arises here is to determine which groups have the
(strict) EKR property. Our first theorem is in line with answering this
question. Before describing our theorems, let us mention a few interesting
results. It has been proved that the alternative groups have the strict EKR
property [8]. In [1], the authors showed that $SL_{2}(q)$ acting on a
$2$-dimensional vector space over $\mathbb{F}_{q}$ has the strict EKR
property. Furthermore, it has been shown that the projective general linear
groups $PGL_{2}(q)$ have the strict EKR property [10], while the groups
$PGL_{3}(q)$ do not so [11]. For more studies, we refer the reader to [6, 9,
12].

In [1], the authors showed that the EKR property holds for $GL_{2}(V)$,
however their result is incomplete. In this paper, we inspire their method and
employ the properties of linear groups and group-action for generalizing their
result and correcting the flaw. We show that $SL_{2}(V)<G\leq GL_{2}(V)$ has
the EKR property and does not have the strict EKR property. Furthermore, we
prove that every intersecting set $\mathcal{F}$ of $SL_{2}(V)<G\leq GL_{2}(V)$
is contained in an intersecting set of size $qd$.

##  2\. Additional notation and auxiliary Lemmas

In this section, we recall some notation and definitions. Also, we prove
several lemmas in order to prove our results.

Assume that $p$ is a prime number and $k\in\mathbb{N}$. We denote a finite
field of order $q=p^{k}$ by $\mathbb{F}_{q}$. Let $V$ be a $2$-dimensional
vector space over $\mathbb{F}_{q}$, and $G$ be a finite group such that
$SL_{2}(V)<G\leq GL_{2}(V)$. Throughout this paper, assume that $\mathcal{F}$
is an intersecting set of $G$ and
$\mathcal{F}_{0}=\mathcal{F}\setminus\\{Id\\}$. For a basis $B$ of $V$ and
$g\in G$, $[g]_{B}$ stands for the matrix representation corresponding to $g$
and for $w\in V\setminus\\{0\\}$, ${\langle w\rangle}$ stands for the
$1$-dimensional subspace of $V$, with $\\{w\\}$ as its basis. We denote the
stabilizer subgroup of a point $v\in V$ by $G_{v}$ while $G_{\langle
w\rangle}$ denotes the stabilizer subgroup of a subspace ${\langle w\rangle}$.

For every $w\in V\setminus\\{0\\}$, set

$H_{\langle w\rangle}=\\{M\in G:\forall v\in V,Mv-v\in\langle w\rangle\\}.$

We define $\rm det(G)$ as the set of determinants of all elements of $G$.

######  Remark 1.

Let $\mathcal{F}$ be an intersecting set of $G$. In this paper we assume that
$Id\in\mathcal{F}$. Because if $x\in\mathcal{F}$, then $Id=x^{-1}x\in
x^{-1}\mathcal{F}$ and $|\mathcal{F}|=|x^{-1}\mathcal{F}|$. So
$x^{-1}\mathcal{F}$ is an intersecting set containing $Id$ with the same size
as $|\mathcal{F}|$. Now we can use $x^{-1}\mathcal{F}$ instead of
$\mathcal{F}$.

######  Lemma 1.

For $w\in V\setminus\\{0\\}$, $H_{\langle w\rangle}$ is a subgroup of $G$ and
$|H_{\langle w\rangle}|=qd$, where $d=|{\rm det(G)}|$.

###### Proof.

Since $Id\in H_{\langle w\rangle}$, $H_{\langle w\rangle}\neq\emptyset$. Let
$M_{1},M_{2}\in H_{\langle w\rangle}$. Then, for every $v\in V$,
$M_{1}v-v,M_{2}v-v\in\langle w\rangle$. Thus, $M_{1}(M_{2}v)-M_{2}v\in\langle
w\rangle$, and hence $M_{1}M_{2}v-M_{2}v+M_{2}v-v\in\langle w\rangle$. This
shows that $M_{1}M_{2}v-v\in\langle w\rangle$. Therefore $M_{1}M_{2}\in
H_{\langle w\rangle}$.
Also, $M^{-1}_{1}v\in V$, so $M_{1}M^{-1}_{1}v-M^{-1}_{1}v\in\langle w\rangle$
and consequently, $M^{-1}_{1}v-v\in\langle w\rangle$. This implies that
$M^{-1}_{1}\in H_{\langle w\rangle}$ and hence $H_{\langle w\rangle}\leq G$.
Now we are going to prove the second part. Assume that $B=\\{v,w\\}$ is a
basis of $V$. Let $g\in H_{\langle w\rangle}\setminus\\{Id\\}$. Since
$gv-v,gw-w$ belong to ${\langle w\rangle}$, we have

$[g]_{B}=\begin{bmatrix}1&0\\\ c&\mu\end{bmatrix},$

where $\mu\in{\rm det(G)}$ and $c\in\mathbb{F}_{q}$. For every
$\begin{pmatrix}\alpha\\\ \beta\end{pmatrix}\in V$, we can see that

$\begin{bmatrix}1&0\\\ c&\mu\end{bmatrix}\begin{pmatrix}\alpha\\\
\beta\end{pmatrix}-\begin{pmatrix}\alpha\\\ \beta\end{pmatrix}\in\langle
w\rangle.$

We can check at once that for every $\mu\in{\rm det(G)}$ and
$c\in\mathbb{F}_{q}$, $\begin{bmatrix}1&0\\\ c&\mu\end{bmatrix}\in G$. This
guarantees that

$H_{\langle w\rangle}=\\{g\in G:[g]_{B}=\begin{bmatrix}1&0\\\
c&\mu\end{bmatrix},{\rm where}~{}\mu\in{\rm det(G)}\ {\rm
and}~{}c\in\mathbb{F}_{q}\\},$

which gives $|H_{\langle w\rangle}|=q|\rm det(G)|$, as wanted. ∎

######  Lemma 2.

Let $v\in V\setminus\\{0\\}$. Then $|G_{v}|=q|{\rm det(G)}|$.

###### Proof.

Since $G$ acts transitively on $V\setminus\\{0\\}$, we have
$[G:G_{v}]=q^{2}-1$. Observe that $|G|=q(q^{2}-1)|{\rm det(G)}|$. So, the
lemma follows.

∎

######  Lemma 3.

Let $w\in V\setminus\\{0\\}$. Then $H_{\langle w\rangle}$ is an intersecting
set of $G$.

###### Proof.

Let $B=\\{v,w\\}$ be a basis of $V$. As mentioned in the proof of Lemma 1, we
have $H_{\langle w\rangle}=\\{g\in G:[g]_{B}=\begin{bmatrix}1&0\\\
c&\mu\end{bmatrix},{\rm where}~{}\mu\in{\rm det(G)}\ {\rm
and}~{}c\in\mathbb{F}_{q}\\}$. Let $g_{1},g_{2}\in H_{\langle w\rangle}$. Then
there exist $\mu_{1},\mu_{2}\in{\rm det(G)}$ and
$c_{1},c_{2}\in\mathbb{F}_{q}$ such that $[g_{1}]_{B}=\begin{bmatrix}1&0\\\
c_{1}&\mu_{1}\end{bmatrix}$ and $[g_{2}]_{B}=\begin{bmatrix}1&0\\\
c_{2}&\mu_{2}\end{bmatrix}$. If $\mu_{1}=\mu_{2}$, then $g_{1}w=g_{2}w$.
Otherwise $g_{1}(v+\alpha w)=g_{2}(v+\alpha w)$, where
$\alpha=(\mu_{2}-\mu_{1})^{-1}(c_{1}-c_{2})$. Thus $H_{\langle w\rangle}$ is
an intersecting set, as wanted.

∎

######  Lemma 4.

Let $B=\\{v,w\\}$ be a basis of $V$ and $\mathcal{F}$ be an intersecting set
of $G$. If $x\in\mathcal{F}_{0}\cap G_{v}$ and $y\in\mathcal{F}_{0}\cap
G_{w}$, then $[x]_{B}=\begin{bmatrix}1&c\\\ 0&\lambda\end{bmatrix}$ and
$[y]_{B}=\begin{bmatrix}1+c\alpha&0\\\ (\lambda-1)\alpha&1\end{bmatrix}$ for
some $\lambda\in\rm det(G)$, $c\in\mathbb{F}_{q}$ and
$\alpha\in\mathbb{F}^{\ast}_{q}$.

###### Proof.

Since $x\in G_{v}\setminus\\{Id\\}$ and $y\in G_{w}\setminus G_{v}$, we have
$[x]_{B}=\begin{bmatrix}1&c\\\ 0&\lambda\end{bmatrix}$ and
$[y]_{B}=\begin{bmatrix}\lambda^{\prime}&0\\\ c^{\prime}&1\end{bmatrix}$,
where $\lambda,\lambda^{\prime}\in\rm det(G)$ and
$c,c^{\prime}\in\mathbb{F}_{q}$. The set $\mathcal{F}$ is an intersecting set
of $G$ and $x,y\in\mathcal{F}$. So, there exists $u\in V\setminus\\{0\\}$ such
that $x(u)=y(u)$. Note that $V={\langle v,w\rangle}$. Hence $u=av+bw$ for some
$a,b\in\mathbb{F}^{\ast}_{q}$ and $ax(v+a^{-1}bw)=x(u)=y(u)=ay(v+a^{-1}bw)$.
Therefore $x(v+\alpha w)=y(v+\alpha w)$, where $\alpha=a^{-1}b$. It follows
that $(1+c\alpha)v+\lambda\alpha w=\lambda^{\prime}v+(c^{\prime}+\alpha)w$.
Consequently, $\lambda^{\prime}=1+c\alpha$ and $c^{\prime}=(\lambda-1)\alpha$.
Also this shows that

$\mathcal{F}_{0}\cap G_{w}\subseteq\\{z\in
G~{}:~{}[z]_{B}=\begin{bmatrix}1+c\gamma&0\\\
(\lambda-1)\gamma&1\end{bmatrix},~{}{\rm
where}~{}\gamma\in\mathbb{F}_{q}^{\ast}\\}.$ (1)

∎

######  Corollary 5.

Let $B=\\{v,w\\}$ be a basis of $V$ and $\mathcal{F}$ be an intersecting set
of $G$. If $\mathcal{F}\cap G_{w}\neq\\{Id\\}$ and $x\in\mathcal{F}_{0}\cap
G_{v}$ such that $[x]_{B}=\begin{bmatrix}1&0\\\ 0&\lambda\end{bmatrix}$, for
some $\lambda\in\rm det(G)$, then $\mathcal{F}\cap G_{v}\subseteq G_{\langle
w\rangle}$.

###### Proof.

Since $\mathcal{F}\cap G_{w}\neq\\{Id\\}$, there exists an element
$y\in\mathcal{F}_{0}\cap G_{w}$. By Lemma 4,

$[y]_{B}=\begin{bmatrix}1&0\\\ (\lambda-1)\alpha&1\end{bmatrix},$ (2)

for some $\alpha\in\mathbb{F}^{\ast}_{q}$. Now, let $z\in\mathcal{F}_{0}\cap
G_{v}$. Then, $[z]_{B}=\begin{bmatrix}1&c^{\prime}\\\
0&\lambda^{\prime}\end{bmatrix}$, for some $\lambda^{\prime}\in\rm det(G)$ and
$c^{\prime}\in\mathbb{F}_{q}$. By (1),

$\mathcal{F}_{0}\cap G_{w}\subseteq\\{w\in
G~{}:~{}[w]_{B}=\begin{bmatrix}1+c^{\prime}\gamma&0\\\
(\lambda-^{\prime}1)\gamma&1\end{bmatrix},~{}{\rm
where}~{}\gamma\in\mathbb{F}_{q}^{\ast}\\}.$

Hence, $[y]_{B}=\begin{bmatrix}1+c^{\prime}\mu&0\\\
(\lambda^{\prime}-1)\mu&1\end{bmatrix},$ for some
$\mu\in\mathbb{F}^{\ast}_{q}$. So, (2) forces $1=1+c^{\prime}\mu$. Since
$\mu\neq 0$, $c^{\prime}=0$. Thus, $z\in G_{\langle w\rangle}$. This shows
that $\mathcal{F}\cap G_{v}\subseteq G_{\langle w\rangle}$, as wanted. ∎

######  Corollary 6.

Let $B=\\{v,w\\}$ be a basis of $V$ and $\mathcal{F}$ be an intersecting set
of $G$. If $\mathcal{F}_{0}\cap G_{v}\neq\emptyset$, then
$|\mathcal{F}_{0}\cap G_{w}|\leq\epsilon$, where

$\epsilon=\begin{cases}q-1,&{\rm if}~{}\mathcal{F}_{0}\cap G_{v}\subseteq
G_{\langle w\rangle},\\\ d-1,&{\rm otherwise},\end{cases}$

and $d=|\rm det(G)|$. Also, if $\mathcal{F}_{0}\cap G_{w}\not\subseteq
G_{\langle v\rangle}$, then $|\mathcal{F}_{0}\cap G_{v}|\leq d-1$.

###### Proof.

Let $x\in\mathcal{F}_{0}\cap G_{v}$. By Lemma 4,
$[x]_{B}=\begin{bmatrix}1&c\\\ 0&\lambda\end{bmatrix}$ where $\lambda\in{\rm
det(G)}$ and $c\in\mathbb{F}_{q}$. By (1),

$\mathcal{F}_{0}\cap G_{w}\subseteq\\{z\in
G~{}:~{}[z]_{B}=\begin{bmatrix}1+c\gamma&0\\\
(\lambda-1)\gamma&1\end{bmatrix},~{}{\rm
where}~{}\gamma\in\mathbb{F}_{q}^{\ast}\\}.$

Thus $|\mathcal{F}_{0}\cap G_{w}|\leq q-1$. If $\mathcal{F}\cap
G_{v}\not\subseteq G_{\langle w\rangle}$, then $c\neq 0$. Also,
$1+c\gamma\in{\rm det(G)}$. So $\gamma\in c^{-1}(1-{\rm det(G)})$. Since
$\gamma\neq 0$, $\gamma\in c^{-1}(1-{\rm det(G)})\setminus\\{0\\}$. It follows
from (1) that $|\mathcal{F}_{0}\cap G_{w}|\leq d-1$, as desired. The same
argument completes the proof for $|\mathcal{F}_{0}\cap G_{v}|$.

∎

######  Corollary 7.

Let $B=\\{v,w\\}$ be a basis of $V$ and $\mathcal{F}$ be an intersecting set
of $G$. If $x,y\in\mathcal{F}$ such that $x\in(G_{v}\cap G_{\langle
w\rangle})\setminus\\{Id\\}$ and $y\in G_{w}\setminus\\{Id\\}$, then
$y(v)=v+c^{\prime}w$, for some $c^{\prime}\in\mathbb{F}_{q}$.

###### Proof.

The proof follows immediately from (1). ∎

##  3\. Erdős-Ko-Rado Theorem for the general linear group and its subgroups

The purpose of this section is to prove analogues of the Erdős-Ko-Rado theorem
for the general linear group of dimension $2$ and its subgroups.

######  Theorem 8.

Let $\mathcal{F}$ be an intersecting set of $G$. Then $|\mathcal{F}|\leq dq$
where $d=|\rm det(G)|$. In particular, $|\mathcal{F}|=dq$ if and only if
$\mathcal{F}$ is either a coset of $G_{v}$ or a coset of $H_{\langle
w\rangle}$ for some $v,w\in V\setminus\\{0\\}$.

###### Proof.

According to Remark 1, assume that $Id\in\mathcal{F}$. Let
$x\in\mathcal{F}_{0}$. Since $Id\in\mathcal{F}$ and $\mathcal{F}$ is an
intersecting set of $G$, there exists $v\in V\setminus\\{0\\}$ such that
$x(v)=v$. This yields $x\in G_{v}$. If $\mathcal{F}\subseteq G_{v}$, then
Lemma 2 completes the proof. Now let $\mathcal{F}\not\subseteq G_{v}$. Note
that for every $a\in\mathbb{F}^{\ast}_{q}$, $G_{v}=G_{av}$. Let
$y\in\mathcal{F}\setminus G_{v}$. Since $Id\in\mathcal{F}$ and $y\not\in
G_{v}$, there exists $w\in V\setminus\\{0\\}$ such that $y(w)=w$ and
$B=\\{v,w\\}$ is a basis of $V$. Observe that $y\in G_{w}\setminus\\{Id\\}$,
so $[y]_{B}=\begin{bmatrix}\lambda&0\\\ c^{\prime}&1\end{bmatrix}$, where
$c^{\prime}\in\mathbb{F}_{q}$ and $\lambda\in\mathbb{F}^{\ast}_{q}$. We
continue the proof in the following cases:

  * (i)

Assume that $\mathcal{F}\cap G_{v}\subseteq G_{\langle w\rangle}$. Then
$\lambda=1$, by Corollary 7. For $t\in\mathbb{F}_{q}$, let $w_{t}=v+tw$.

    * i.a)

If there exists $t\in\mathbb{F}^{\ast}_{q}$ such that $\mathcal{F}\cap
G_{w_{t}}\not\subseteq G_{\langle w\rangle}$, then there is
$z\in(\mathcal{F}\cap G_{w_{t}})\setminus G_{\langle w\rangle}$. Since
$z,y\in\mathcal{F}_{0}$ and $\mathcal{F}$ is an intersecting set of $G$, there
exists $u\in V\setminus\\{0\\}$ such that $y(u)=z(u)$. If $u=v$, then
$z(v)=y(v)=v+c^{\prime}w$. We can see that
$v+tw=z(v+tw)=z(v)+tz(w)=v+c^{\prime}w+tz(w)$. Therefore
$z(w)=t^{-1}(tw-c^{\prime}w)\in{\langle w\rangle}$. So $z\in G_{\langle
w\rangle}$. This is a contradiction. If $u=v+\alpha w$ for some
$\alpha\in\mathbb{F}^{\ast}_{q}$, then $v+tw+(\alpha-t)z(w)=z(v+\alpha
w)=y(v+\alpha w)=v+c^{\prime}w+\alpha w$, for some
$c^{\prime}\in\mathbb{F}_{q}$. Thus, if $\alpha\neq t$, then
$z(w)=(\alpha-t)^{-1}(c^{\prime}+\alpha-t)w\in{\langle w\rangle}$ which is a
contradiction. Also if $\alpha=t$, then $y(v+tw)=z(v+tw)=v+tw$. So, $y(v)=v$,
consequently $y\in G_{v}$, which is a contradiction.

    * i.b)

Let for every $t\in\mathbb{F}^{\ast}_{q}$, $\mathcal{F}\cap G_{w_{t}}\subseteq
G_{\langle w\rangle}$. Note that $\\{w_{t}:t\in\mathcal{F}_{q}\\}\cup\\{w\\}$
are pairwise linearly independent and for every $u\in V$, either $u\in{\langle
w\rangle}$ or there exists $t\in\mathbb{F}_{q}$ such that
$u\in{\langle{w_{t}}\rangle}$. Since $\mathcal{F}$ is an intersecting set of
$G$, for every $g\in\mathcal{F}$, there exists $u\in V\setminus\\{0\\}$ such
that $g(u)=Id(u)=u$. So, $g\in G_{u}$. Consequently,

$\mathcal{F}=(\dot{\bigcup_{t\in\mathbb{F}_{q}}}\mathcal{F}_{0}\cap
G_{w_{t}})\dot{\cup}(\mathcal{F}_{0}\cap G_{w})\dot{\cup}\\{Id\\}.$ (3)

If $g\in\mathcal{F}_{0}\cap G_{v}$, then $gv-v=0\in{\langle w\rangle}$ and
$g(\alpha v+w)-(\alpha v+w)\in{\langle w\rangle}$ for every
$\alpha\in\mathbb{F}$, because $g\in\mathcal{F}_{0}\cap G_{v}\subseteq
G_{\langle w\rangle}$. So $g\in H_{\langle w\rangle}$. If
$t\in\mathbb{F}^{\ast}_{q}$ and $g\in\mathcal{F}_{0}\cap G_{w_{t}}$, then

$\displaystyle gv-v=g(v+tw-tw)-v=v+tw-tg(w)-v$ $\displaystyle=tw-
tg(w)\in{\langle w\rangle},$

because $g\in\mathcal{F}_{0}\cap G_{w_{t}}\subseteq G_{\langle w\rangle}$.
Also

$\displaystyle g(\alpha v+w)-(\alpha v+w)$
$\displaystyle=\alpha(v+tw)+(-t\alpha+1)g(w)-(\alpha v+w)$
$\displaystyle=(\alpha t-1)w+(-t\alpha+1)g(w)\in{\langle w\rangle}$

for every $\alpha\in\mathbb{F}_{q}$. Therefore $g\in H_{\langle w\rangle}$.
Observe that if $g\in G_{w}$, then $g\in H_{\langle w\rangle}$. Thus
$\mathcal{F}\subseteq H_{\langle w\rangle}$. So Lemma 1 completes the proof.

  * (ii)

If $\mathcal{F}\cap G_{v}\subseteq G_{\langle w_{t}\rangle}$, for some
$t\in\mathbb{F}^{\ast}_{q}$, then replacing $w$ and $w_{t}$ in Case (i)
completes the proof. Also, if $\mathcal{F}_{0}\cap G_{w}\subseteq G_{\langle
v\rangle}$, then replacing $v$ and $w$ in Case(i) completes the proof. The
same reasoning completes the proof when $\mathcal{F}_{0}\cap
G_{w_{t}}\subseteq G_{\langle v\rangle}$, $\mathcal{F}_{0}\cap
G_{w_{t}}\subseteq G_{\langle w\rangle}$, $\mathcal{F}_{0}\cap G_{w}\subseteq
G_{\langle{w_{t}}\rangle}$ or $\mathcal{F}_{0}\cap G_{w}\subseteq
G_{\langle{v}\rangle}$, for some $t\in\mathbb{F}_{q}^{\ast}$.

  * (iii)

Assume that for every $t\in\mathbb{F}^{\ast}_{q}$, $\mathcal{F}_{0}\cap
G_{w}\not\subseteq G_{\langle v\rangle},G_{\langle{w_{t}}\rangle}$,
$\mathcal{F}_{0}\cap G_{v}\not\subseteq G_{\langle
w\rangle},G_{\langle{w_{t}}\rangle}$, and $\mathcal{F}_{0}\cap
G_{w_{t}}\not\subseteq G_{\langle v\rangle},G_{\langle w\rangle}$. Then
Corollary 6 and (3) show that $|\mathcal{F}|\leq(q+1)(d-1)+1<qd$. So, the
theorem follows.

∎

######  Theorem 9.

Every intersecting set of $G$ is contained in an intersecting set of size
$qd$.

###### Proof.

Let $\mathcal{F}$ be an intersecting set of $G$ such that
$\mathcal{F}\not\subseteq G_{u}$, for every $u\in V-\\{0\\}$. By Remark 1, we
assume that $Id\in\mathcal{F}$. Let $x_{0}\in\mathcal{F}_{0}$. Since
$\mathcal{F}$ is an intersecting set of $G$ and $Id\in\mathcal{F}$,
$x_{0}(v)=Id(v)$, for some $v\in V\setminus\\{0\\}$. So, we have
$x_{0}\in\mathcal{F}_{0}\cap G_{v}$. Note that $\mathcal{F}\not\subseteq
G_{v}$. This implies that there exists a $y_{0}\in\mathcal{F}_{0}\setminus
G_{v}$. Now, $y_{0}\in\mathcal{F}$ and $\mathcal{F}$ is an intersecting set of
$G$. Hence, we can find a $w\in V\setminus{\langle v\rangle}$ such that
$y_{0}\in G_{w}$. Set $w_{t}=v+tw$, for $t\in\mathbb{F}_{q}^{\ast}$ and let
$B_{0}=\\{v,w\\}$. We have $B_{0}$ is a basis of $V$. By Lemma 4,

$[x_{0}]_{B_{0}}=\begin{bmatrix}1&c_{0}\\\ 0&\lambda_{0}\end{bmatrix},$ (4)

where $c_{0}\in\mathbb{F}_{q}$ and $\lambda_{0}\in{\rm det(G)}$. If $c_{0}=0$,
then $\mathcal{F}\cap G_{v}\subseteq G_{\langle w\rangle}$, by Corollary 5. It
follows from Case (i) in the proof of Theorem 8 that $\mathcal{F}\subseteq
H_{\langle w\rangle}$, as desired. If $\lambda_{0}=1$, then (1) shows that
$\mathcal{F}\cap G_{w}\subseteq G_{\langle v\rangle}$. So, Case (i) in the
proof of Theorem 8 guarantees that $\mathcal{F}\subseteq H_{\langle
v\rangle}$, as desired. Finally let $c_{0}\neq 0$ and $\lambda_{0}\neq 1$.
Then,
$x_{0}(v+(\lambda_{0}-1)c_{0}^{-1}w)=\lambda_{0}(v+(\lambda_{0}-1)c_{0}^{-1}w)$.
Thus, $x_{0}\in G_{\langle w_{\alpha}\rangle}$, where
$\alpha=(\lambda_{0}-1)c_{0}^{-1}$. If $z\in\mathcal{F}_{0}\cap G_{v}$, then
Lemma 4 shows that $[z]_{B_{0}}=\begin{bmatrix}1&c\\\ 0&\lambda\end{bmatrix}$,
where $c\in\mathbb{F}_{q}$ and $\lambda\in{\rm det(G)}$. By (1) and (4),
$1+\gamma_{0}c_{0}=1+\gamma c$ and
$(1-\lambda_{0})\gamma_{0}=(1-\lambda)\gamma$, for some
$\gamma_{0},\gamma\in\mathbb{F}_{q}^{*}$. Then, we have
$z(v+(\lambda-1)c^{-1}w)=\lambda(v+(\lambda-1)c^{-1}w)$. However,
$(\lambda_{0}-1)c_{0}^{-1}=(\lambda-1)\gamma\gamma_{0}^{1}c^{-1}\gamma^{1}\gamma_{0}=(\lambda-1)c^{-1}$.
Hence, $z\in G_{\langle w_{\alpha}\rangle}$. Consequently,
$\mathcal{F}_{0}\cap G_{v}\subseteq G_{\langle w_{\alpha}\rangle}$, where
$\alpha=(\lambda_{0}-1)c_{0}^{-1}$. Assume that $t\in\mathbb{F}_{q}*$ and
$x_{t}\in\mathcal{F}_{0}\cap G_{w_{t}}$. Set $B_{t}=\\{v,w_{t}\\}$. Then,
$B_{t}$ is a basis of $V$. We can check at once that
$[x_{0}]_{B_{t}}=\begin{bmatrix}1&1+tc_{0}-\lambda_{0}\\\
0&\lambda_{0}\end{bmatrix}$. So, (1) shows that
$[x_{t}]_{B_{t}}=\begin{bmatrix}1+(1+tc_{0}-\lambda_{0})\gamma_{t}&0\\\
(\lambda_{0}-1)\gamma_{t}&1\end{bmatrix}$, for some
$\gamma_{t}\in\mathbb{F}_{q}^{\ast}$. However, $v+\alpha w=(1-\alpha
t^{-1})v+\alpha t^{-1}w_{t}$ and $x_{t}((1-\alpha t^{-1})v+\alpha
t^{-1}w_{t})=(1+(1+tc_{0}-\lambda_{0})\gamma_{t})((1-\alpha t^{-1})v+\alpha
t^{-1}w_{t})$. Hence, $x_{t}\in G_{\langle w_{\alpha}\rangle}$. Thus,
$\mathcal{F}_{0}\cap G_{w_{t}}\subseteq G_{\langle w_{\alpha}\rangle}$. The
same reasoning shows that $\mathcal{F}_{0}\cap G_{w}\subseteq G_{\langle
w_{\alpha}\rangle}$. Thus, Sub-Case (i.b) in the proof of Theorem 8 shows that
$\mathcal{F}\subseteq H_{\langle w_{\alpha}\rangle}$, as desired. ∎

Acknowledgement The author is grateful to Professor Karen Meagher for drawing
his attention to the flaw in [1], and constructive comments that improved the
paper.

## References

  * [1] M. Ahanjideh and N. Ahanjideh, Erdős-Ko-Rado theorem in some linear groups and some projective special linear group, Studia Sci. Math. Hungar., 51(1) (2014) 83–91.
  * [2] B. Ahmadi and K. Meagher, The Erdős-Ko-Rado property for some permutation groups, Australas. J. Combin., 61 (2015) 23–41.
  * [3] P. Cameron and C.Y. Ku, Intersecting families of permutations, European J. Combin., 24 (2003) 881–890.
  * [4] P. Erdős, C. Ko, and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser., 12 (1961) 313–320.
  * [5] P. Frankl and M. Deza, On the maximum number of permutations with given maximal or minimal distance, J. Combin. Theory Ser. A, 22(3) (1977) 352 – 360.
  * [6] C. Godsil and K. Meagher, A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations, European J. Combin., 30 (2009) 404–414.
  * [7] A.J.W. Hilton and E.C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser., 18 (1) (1967) 369–384.
  * [8] C.Y. Ku and T.W.H. Wong, Intersecting families in the alternating group and direct product of symmetric groups, Electronic Journal of Combinatorics, 14(1) (2007) R25.
  * [9] K. Meagher, An Erdős-Ko-Rado theorem for the group $PSU(3,q)$, Des. Codes Cryptogr., 87 (2019) 717–744.
  * [10] K. Meagher and P. Spiga, An Erdős-Ko-Rado theorem for the derangement graph of PGL(2, q) acting on the projective line, J. Combin. Theory Ser. A, 118(2) (2011) 532–544,
  * [11] K. Meagher and P. Spiga, An Erdős-Ko-Rado-type theorem for ${PGL}_{3}(q)$, SIAM Journal of Discrete Math, 28 (2014) 918–941.
  * [12] K. Meagher, P. Spiga and P.H. Tiep, An Erdős-Ko-Rado theorem for finite 2-transitive groups, European J. Combin., 55 (2016) 100–118.


the lowest point in the performance curve in Figure 12. In other words, the
$H_{\text{edge}}(\mathcal{G})$ where SGC-1 and GCN perform worst is where
$g(h)$ gets the smallest value, instead of the point with the smallest edge
homophily value, i.e., $H_{\text{edge}}(\mathcal{G})=0$. This reveals the
advantage of $H_{\text{agg}}(\mathcal{G})$ over $H_{\text{edge}}(\mathcal{G})$
by taking use of the similarity matrix.

##  Appendix E Details of Gradient Calculation in equation 6

###  E.1 Derivation in Matrix Form

This derivation is similar to [30].

In output layer, we have

$\displaystyle Y$
$\displaystyle=\text{softmax}(\hat{A}XW)\equiv\text{softmax}(Y^{\prime})=\left(\exp(Y^{\prime})\bm{1}_{C}\bm{1}_{C}^{T}\right)^{-1}\odot\exp(Y^{\prime})>0$
$\displaystyle\mathcal{L}$ $\displaystyle=-\mathrm{trace}(Z^{T}\log Y)$

where $\bm{1}_{C}\in\mathcal{R}^{C\times 1}$, $(\cdot)^{-1}$ is point-wise
inverse function and each element of $Y$ is positive. Then

$\displaystyle d\mathcal{L}=-\mathrm{trace}\left(Z^{T}((Y)^{-1}\odot
dY)\right)=-\mathrm{trace}\left(Z^{T}\left(\left(\text{softmax}(Y^{\prime})\right)^{-1}\odot
d\ \text{softmax}(Y^{\prime})\right)\right)$

Note that

$\displaystyle d\ \text{softmax}(Y^{\prime})=$
$\displaystyle-\left(\exp(Y^{\prime})\bm{1}_{C}\bm{1}_{C}^{T}\right)^{-2}\odot[(\exp(Y^{\prime})\odot
dY^{\prime})\bm{1}_{C}\bm{1}_{C}^{T}]\odot\exp(Y^{\prime})$
$\displaystyle+\left(\exp(Y^{\prime})\bm{1}_{C}\bm{1}_{C}^{T}\right)^{-1}\odot(\exp(Y^{\prime})\odot
dY^{\prime})$ $\displaystyle=$
$\displaystyle-\text{softmax}(Y^{\prime})\odot\left(\exp(Y^{\prime})\bm{1}_{C}\bm{1}_{C}^{T}\right)^{-1}\odot[(\exp(Y^{\prime})\odot
dY^{\prime})\bm{1}_{C}\bm{1}_{C}^{T}]$
$\displaystyle+\text{softmax}(Y^{\prime})\odot dY^{\prime}$ $\displaystyle=$
$\displaystyle\
\text{softmax}(Y^{\prime})\odot\left(-\left(\exp(Y^{\prime})\bm{1}_{C}\bm{1}_{C}^{T}\right)^{-1}\odot\left[(\exp(Y^{\prime})\odot
dY^{\prime})\bm{1}_{C}\bm{1}_{C}^{T}\right]+dY^{\prime}\right)$

Then,

$\displaystyle d\mathcal{L}=$
$\displaystyle-\mathrm{trace}\Bigg{(}Z^{T}\bigg{(}(\text{softmax}(Y^{\prime}))^{-1}\odot\bigg{[}\text{softmax}(Y^{\prime})\odot\bigg{(}-\left(\exp(Y^{\prime})\bm{1}_{C}\bm{1}_{C}^{T}\right)^{-1}$
$\displaystyle\odot\left[(\exp(Y^{\prime})\odot
dY^{\prime})\bm{1}_{C}\bm{1}_{C}^{T}\right]+dY^{\prime}\bigg{)}\bigg{]}\bigg{)}\Bigg{)}$
$\displaystyle=$
$\displaystyle-\mathrm{trace}\left(Z^{T}\left(-\left(\exp(Y^{\prime})\bm{1}_{C}\bm{1}_{C}^{T}\right)^{-1}\odot\left[(\exp(Y^{\prime})\odot
dY^{\prime})\bm{1}_{C}\bm{1}_{C}^{T}\right]+dY^{\prime}\right)\right)$
$\displaystyle=$
$\displaystyle\mathrm{trace}\left(\left(\left(Z\odot\left(\exp(Y^{\prime})\bm{1}_{C}\bm{1}_{C}^{T}\right)^{-1}\right)\bm{1}_{C}\bm{1}_{C}^{T}\right)^{T}\left[\exp(Y^{\prime})\odot
dY^{\prime}\right]-Z^{T}dY^{\prime}\right)$ $\displaystyle=$
$\displaystyle\mathrm{trace}\left(\left(\exp(Y^{\prime})\odot\left(\left(Z\odot\left(\exp(Y^{\prime})\bm{1}_{C}\bm{1}_{C}^{T}\right)^{-1}\right)\bm{1}_{C}\bm{1}_{C}^{T}\right)\right)^{T}dY^{\prime}-Z^{T}dY^{\prime}\right)$
$\displaystyle=$
$\displaystyle\mathrm{trace}\left(\left(\exp(Y^{\prime})\odot\left(\exp(Y^{\prime})\bm{1}_{C}\bm{1}_{C}^{T}\right)^{-1}\right)^{T}dY^{\prime}-Z^{T}dY^{\prime}\right)$
$\displaystyle=$
$\displaystyle\mathrm{trace}\left((\text{softmax}(Y^{\prime})-Z)^{T}dY^{\prime}\right)$

where the 4-th equation holds due to
$\left(Z\odot\left(\exp(Y^{\prime})\bm{1}_{C}\bm{1}_{C}^{T}\right)^{-1}\right)\bm{1}_{C}\bm{1}_{C}^{T}=\left(\exp(Y^{\prime})\bm{1}_{C}\bm{1}_{C}^{T}\right)^{-1}$.
Thus, we have

$\frac{d\mathcal{L}}{dY^{\prime}}=\text{softmax}(Y^{\prime})-Z=Y-Z$

For $Y^{\prime}$ and $W$, we have

$\displaystyle dY^{\prime}$ $\displaystyle=\hat{A}XdW\text{ and
}d\mathcal{L}=\text{trace}\left(\frac{d\mathcal{L}}{dY^{\prime}}^{T}dY^{\prime}\right)=\text{trace}\left(\frac{d\mathcal{L}}{dY^{\prime}}^{T}\hat{A}X\
dW\right)=\text{trace}\left(\frac{d\mathcal{L}}{dW}^{T}\ dW\right)$

To get $\frac{d\mathcal{L}}{dW}$ we have,

$\displaystyle\frac{d\mathcal{L}}{dW}=X^{T}\hat{A}^{T}\frac{d\mathcal{L}}{dY^{\prime}}=X^{T}\hat{A}^{T}(Y-Z)$
(13)

###  E.2 Component-wise Derivation

Denote $\tilde{X}=XW$. We rewrite $\cal L$ as follows:

$\displaystyle\mathcal{L}$
$\displaystyle=-\mathrm{trace}\left(Z^{T}\log\left((\exp({Y^{\prime}})\bm{1}_{C}\bm{1}_{C}^{T})^{-1}\odot\exp({Y^{\prime}})\right)\right)$
$\displaystyle=-\mathrm{trace}\left(Z^{T}\left(-\log(\exp({Y^{\prime}})\bm{1}_{C}\bm{1}_{C}^{T})+{Y^{\prime}}\right)\right)$
$\displaystyle=-\mathrm{trace}\left(Z^{T}{Y^{\prime}}\right)+\mathrm{trace}\left(Z^{T}\log\left(\exp({Y^{\prime}})\bm{1}_{C}\bm{1}_{C}^{T}\right)\right)$
$\displaystyle=-\mathrm{trace}\left(Z^{T}\hat{A}XW\right)+\mathrm{trace}\left(Z^{T}\log\left(\exp({Y^{\prime}})\bm{1}_{C}\bm{1}_{C}^{T}\right)\right)$
$\displaystyle=-\mathrm{trace}\left(Z^{T}\hat{A}XW\right)+\mathrm{trace}\left(\bm{1}_{C}^{T}\log\left(\exp({Y^{\prime}})\bm{1}_{C}\right)\right)$

Expand $\mathcal{L}$ component-wisely, we have

$\displaystyle\mathcal{L}$
$\displaystyle=-\sum\limits_{i=1}^{N}\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}Z_{i,:}\tilde{X}_{j:}^{T}+\sum\limits_{i=1}^{N}\log\left(\sum\limits_{c=1}^{C}\exp(\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}\tilde{X}_{j,c})\right)$
$\displaystyle=-\sum\limits_{i=1}^{N}\log\left(\exp\left(\sum\limits_{c=1}^{C}\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}Z_{i,c}\tilde{X}_{j,c}\right)\right)+\sum\limits_{i=1}^{N}\log\left(\sum\limits_{c=1}^{C}\exp\left(\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}\tilde{X}_{j,c}\right)\right)$
$\displaystyle=-\sum\limits_{i=1}^{N}\log\frac{\exp\left(\sum\limits_{c=1}^{C}\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}Z_{i,c}\tilde{X}_{j,c}\right)}{\left(\sum\limits_{c=1}^{C}\exp(\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}\tilde{X}_{j,c})\right)}$

Note that $\sum\limits_{c=1}^{C}Z_{j,c}=1$ for any $j$. Consider the
derivation of $\mathcal{L}$ over $\tilde{X}_{j^{\prime},c^{\prime}}$:

$\begin{split}\allowdisplaybreaks&\frac{d\mathcal{L}}{d\tilde{X}_{j^{\prime},c^{\prime}}}=-\sum\limits_{i=1}^{N}\frac{\sum\limits_{c=1}^{C}\exp(\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}\tilde{X}_{j,c})}{\exp\left(\sum\limits_{c=1}^{C}\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}Z_{i,c}\tilde{X}_{j,c}\right)}\\\
&\times\left(\frac{\left(\hat{A}_{i,j^{\prime}}Z_{i,c^{\prime}}\right)\exp\left(\sum\limits_{c=1}^{C}\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}Z_{i,c}\tilde{X}_{j,c}\right)\left(\sum\limits_{c=1}^{C}\exp(\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}\tilde{X}_{j,c})\right)}{\left(\sum\limits_{c=1}^{C}\exp(\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}\tilde{X}_{j,c})\right)^{2}}\right.\\\
&\left.-\frac{\left(\hat{A}_{i,j^{\prime}}\right)\exp\left(\sum\limits_{c=1}^{C}\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}Z_{i,c}\tilde{X}_{j,c}\right)\left(\exp(\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}\tilde{X}_{j,c^{\prime}})\right)}{\left(\sum\limits_{c=1}^{C}\exp(\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}\tilde{X}_{j,c})\right)^{2}}\right)\\\
=&-\sum\limits_{i=1}^{N}\left(\frac{\left(\hat{A}_{i,j^{\prime}}Z_{i,c^{\prime}}\right)\left(\sum\limits_{c=1}^{C}\exp(\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}\tilde{X}_{j,c})\right)-\left(\hat{A}_{i,j^{\prime}}\right)\left(\exp(\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}\tilde{X}_{j,c^{\prime}})\right)}{\left(\sum\limits_{c=1}^{C}\exp(\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}\tilde{X}_{j,c})\right)}\right)\\\
=&-\sum\limits_{i=1}^{N}\left(\hat{A}_{i,j^{\prime}}\frac{\left(\sum\limits_{c=1,c\neq
c^{\prime}}^{C}(Z_{i,c^{\prime}})\exp(\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}\tilde{X}_{j,c})\right)+\left(Z_{i,c^{\prime}}-1\right)\left(\exp(\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}\tilde{X}_{j,c^{\prime}})\right)}{\left(\sum\limits_{c=1}^{C}\exp(\sum\limits_{j\in\mathcal{N}_{i}}\hat{A}_{i,j}\tilde{X}_{j,c})\right)}\right)\\\
=&-\sum\limits_{i=1}^{N}\hat{A}_{i,j^{\prime}}\left(Z_{i,c^{\prime}}\hat{P}(Y_{i}\neq
c^{\prime})+(Z_{i,c^{\prime}}-1)\hat{P}(Y_{i}=c^{\prime})\right)\\\
=&-\sum\limits_{i=1}^{N}\hat{A}_{i,j^{\prime}}\left(Z_{i,c^{\prime}}-\hat{P}(Y_{i}=c^{\prime})\right)\end{split}$
(14)

Writing the above in matrix form, we have

$\frac{d\mathcal{L}}{d\tilde{X}}=\hat{A}(Z-Y),\
\frac{d\mathcal{L}}{d\tilde{W}}=X^{T}\hat{A}^{T}(Z-Y),\ \Delta
Y^{\prime}\propto\hat{A}XX^{T}\hat{A}^{T}(Z-Y)$ (15)

##  Appendix F Proof of Proposition 1

###### Proof.

According to the given assumptions, for node $v$, we have
$\hat{A}_{v,k}=\frac{1}{d+1}$, the expected number of intra-class edges is
$dh$ (here the self-loop edge introduced by $\hat{A}$ is not counted based on
the definition of edge homophily and data generation process) and inter-class
edges is $(1-h)d$. Suppose there are $C\geq 2$ classes. Consider matrix
$\hat{A}Z$,

Then, we have
$\mathbb{E}\left[(\hat{A}Z)_{v,c}\right]=\mathbb{E}\left[\sum\limits_{k\in\mathcal{V}}\hat{A}_{v,k}\textbf{1}_{\\{Z_{k,:}=e_{c}^{T}\\}}\right]=\sum\limits_{k\in\mathcal{V}}\frac{\mathbb{E}\left[\textbf{1}_{\\{Z_{k,:}=e_{c}^{T}\\}}\right]}{d+1}$,
where $\bm{1}$ is the indicator function.

When $v$ is in class $c$, we have
$\sum\limits_{k\in\mathcal{V}}\frac{\mathbb{E}\left[\textbf{1}_{\\{Z_{k,:}=e_{c}^{T}\\}}\right]}{d+1}=\frac{hd+1}{d+1}$
($hd+1=hd$ intra-class edges $+$ 1 self-loop introduced by $\hat{A}$).

When $v$ is not in class $c$, we have
$\sum\limits_{k\in\mathcal{V}}\frac{\mathbb{E}\left[\textbf{1}_{\\{Z_{k,:}=e_{c}^{T}\\}}\right]}{d+1}=\frac{(1-h)d}{(C-1)(d+1)}$
($(1-h)d$ inter-class edges uniformly distributed in the other $C-1$ classes).

For nodes $v,u$, we have $(\hat{A}Z)_{v,:},(\hat{A}Z)_{u,:}\in\mathbb{R}^{C}$
and since elements in $\hat{A}_{v,k}$ and $\hat{A}_{u,k^{\prime}}$ are
independently generated for all $k,k^{\prime}\in\mathcal{V}$, we have

$\displaystyle\mathbb{E}\left[(\hat{A}Z)_{v,c}(\hat{A}Z)_{u,c}\right]$
$\displaystyle=\mathbb{E}\left[(\sum\limits_{k\in\mathcal{V}}\hat{A}_{v,k}\textbf{1}_{\\{Z_{k,:}=e_{c}^{T}\\}})(\sum\limits_{k^{\prime}\in\mathcal{V}}\hat{A}_{u,k^{\prime}}\textbf{1}_{\\{Z_{k^{\prime},:}=e_{c}^{T}\\}})\right]$
$\displaystyle=\mathbb{E}\left[(\sum\limits_{k\in\mathcal{V}}\hat{A}_{v,k}\textbf{1}_{\\{Z_{k,:}=e_{c}^{T}\\}})\right]\mathbb{E}\left[(\sum\limits_{k^{\prime}\in\mathcal{V}}\hat{A}_{u,k^{\prime}}\textbf{1}_{\\{Z_{k^{\prime},:}=e_{c}^{T}\\}})\right]$

Thus,

$\displaystyle\mathbb{E}\left[S(\hat{A},Z)_{v,u}\right]$
$\displaystyle=\mathbb{E}\left[<(\hat{A}Z)_{v,:},(\hat{A}Z)_{u,:}>\right]=\sum\limits_{c}\mathbb{E}\left[(\sum\limits_{k\in\mathcal{V}}\hat{A}_{v,k}\textbf{1}_{\\{Z_{k,:}=e_{c}^{T}\\}})\right]\mathbb{E}\left[(\sum\limits_{k^{\prime}\in\mathcal{V}}\hat{A}_{u,k^{\prime}}\textbf{1}_{\\{Z_{k^{\prime},:}=e_{c}^{T}\\}})\right]$
$\displaystyle=\left\\{\begin{array}[]{ll}\left(\frac{hd+1}{d+1}\right)^{2}+\frac{\left((1-h)d\right)^{2}}{(C-1)(d+1)^{2}},&\text{$u,v$
are in the same class}\\\
\frac{2(hd+1)(1-h)d}{(C-1)(d+1)^{2}}+\frac{(C-2)(1-h)^{2}d^{2}}{(C-1)^{2}(d+1)^{2}},&\text{$u,v$
are in different classes}\end{array}\right.$

For nodes $u_{1}$, $u_{2}$, and $v$, where $Z_{u_{1},:}=Z_{v,:}$ and
$Z_{u_{2},:}\neq Z_{v,:}$,

$\displaystyle g(h)$
$\displaystyle\equiv\mathbb{E}\left[S(\hat{A},Z)_{v,u_{1}}\right]-\mathbb{E}\left[S(\hat{A},Z)_{v,u_{2}}\right]$
(16)
$\displaystyle=\frac{(C-1)^{2}(hd+1)^{2}+(C-1)\left[(1-h)d\right]^{2}-(C-1)\left(2(hd+1)(1-h)d\right)-(C-2)\left[(1-h)d\right]^{2}}{(C-1)^{2}(d+1)^{2}}$
$\displaystyle=\left(\frac{(C-1)(hd+1)-(1-h)d}{(C-1)(d+1)}\right)^{2}$

Setting $g(h)=0$, we obtain the optimal $h$:

$h=\frac{d+1-C}{Cd}$ (17)

For the data generation process in the synthetic experiments, we fix
$d_{\text{intra}}$, then $d=d_{\text{intra}}/h$, which is a function of $h$.
We change $d$ in equation 17 to $d_{\text{intra}}/h$, leading to

$h=\frac{d_{\text{intra}}/h+1-C}{Cd_{\text{intra}}/h}$ (18)

It is easy to observe that $h$ satisfying equation 18 still makes $g(h)=0$,
when $d$ in $g(h)$ is replaced by $d_{\text{intra}}/h$. From equation 18 we
obtain the optimal $h$ in terms of $d_{\text{intra}}$:

$h=\frac{d_{\text{intra}}}{Cd_{\text{intra}}+C-1}$

∎

###  F.1 An Extension of Proposition 1

Base on the definition of aggregation similarity, we have

$\displaystyle S_{\text{agg}}\left(S(\hat{A},Z)\right)$
$\displaystyle=\frac{\left|\left\\{v\,\big{|}\,\mathrm{Mean}_{u}\big{(}\\{S(\hat{A},Z)_{v,u}|Z_{u,:}=Z_{v,:}\\}\big{)}\geq\mathrm{Mean}_{u}\big{(}\\{S(\hat{A},Z)_{v,u}|Z_{u,:}\neq
Z_{v,:}\\}\big{)}\right\\}\right|}{\left|\mathcal{V}\right|}$
$\displaystyle=\frac{\sum\limits_{v\in\mathcal{V}}\bm{1}_{\left\\{\mathrm{Mean}_{u}\big{(}\\{S(\hat{A},Z)_{v,u}|Z_{u,:}=Z_{v,:}\\}\big{)}\geq\mathrm{Mean}_{u}\big{(}\\{S(\hat{A},Z)_{v,u}|Z_{u,:}\neq
Z_{v,:}\\}\big{)}\right\\}}}{\left|\mathcal{V}\right|}$

Then,

$\displaystyle\mathbb{E}\left(S_{\text{agg}}\left(S(\hat{A},Z)\right)\right)$
$\displaystyle=\mathbb{E}\left(\frac{\sum\limits_{v\in\mathcal{V}}\bm{1}_{\left\\{\mathrm{Mean}_{u}\big{(}\\{S(\hat{A},Z)_{v,u}|Z_{u,:}=Z_{v,:}\\}\big{)}\geq\mathrm{Mean}_{u}\big{(}\\{S(\hat{A},Z)_{v,u}|Z_{u,:}\neq
Z_{v,:}\\}\big{)}\right\\}}}{\left|\mathcal{V}\right|}\right)$
$\displaystyle=\frac{\sum\limits_{v\in\mathcal{V}}\mathbb{P}\left(\mathrm{Mean}_{u}\big{(}\\{S(\hat{A},Z)_{v,u}|Z_{u,:}=Z_{v,:}\\}\big{)}\geq\mathrm{Mean}_{u}\big{(}\\{S(\hat{A},Z)_{v,u}|Z_{u,:}\neq
Z_{v,:}\\}\big{)}\right)}{\left|\mathcal{V}\right|}$
$\displaystyle=\mathbb{P}\left(\mathrm{Mean}_{u}\big{(}\\{S(\hat{A},Z)_{v,u}|Z_{u,:}=Z_{v,:}\\}\big{)}-\mathrm{Mean}_{u}\big{(}\\{S(\hat{A},Z)_{v,u}|Z_{u,:}\neq
Z_{v,:}\\}\big{)}\geq 0\right)$

Consider the random variable

$RV=\mathrm{Mean}_{u}\big{(}\\{S(\hat{A},Z)_{v,u}|Z_{u,:}=Z_{v,:}\\}\big{)}-\mathrm{Mean}_{u}\big{(}\\{S(\hat{A},Z)_{v,u}|Z_{u,:}\neq
Z_{v,:}\\}\big{)}$

Since $RV$ is symmetrically distributed and under the conditions in
proposition 1, its expectation is $\mathbb{E}[RV]=g(h)$ as showed in equation
16. Since the minimum of $g(h)$ is $0$ and $RV$ is symmetrically distributed,
we have $\mathbb{P}(RV\geq 0)\geq 0.5$ and this can explain why
$H_{\text{agg}}(\mathcal{G})$ is always greater than 0.5 in many real-world
tasks.

##  Appendix G Proof of Theorem 1

###### Proof.

Define $W_{v}^{c}=(\hat{A}Z)_{v,c}$. Then,

$W_{v}^{c}=\sum\limits_{k\in\mathcal{V}}\hat{A}_{v,k}\bm{1}_{\\{Z_{k,:}=e_{c}^{T}\\}}\in[0,1],\
\ \sum\limits_{c=1}^{C}W_{v}^{c}=1$

Note that

$S(I-\hat{A},Z)=(I-\hat{A})ZZ^{T}(I-\hat{A})^{T}=ZZ^{T}+\hat{A}ZZ^{T}\hat{A}^{T}-\hat{A}ZZ^{T}-ZZ^{T}\hat{A}^{T}$
(19)

For any node $v$, let the class $v$ belongs to be denoted by $c_{v}$. For two
nodes $v,u$, if $Z_{v,:}\neq Z_{u,:}$, we have

$\displaystyle(ZZ^{T})_{v,u}=0$
$\displaystyle(\hat{A}ZZ^{T}\hat{A}^{T})_{v,u}=\sum\limits_{c=1}^{C}W_{v}^{c}W_{u}^{c}$
$\displaystyle(\hat{A}ZZ^{T})_{v,u}=W_{v}^{c_{u}}$
$\displaystyle(ZZ^{T}\hat{A}^{T})_{v,u}=(\hat{A}ZZ^{T})_{u,v}=W_{u}^{c_{v}}$

Then, from equation 19 it follows that

$\displaystyle(S(I-\hat{A},Z))_{v,u}=\sum\limits_{c=1}^{C}W_{v}^{c}W_{u}^{c}-W_{v}^{c_{u}}-W_{u}^{c_{v}}$

When $C=2$,

$\displaystyle
S(I-\hat{A},Z)_{v,u}=W_{v}^{c_{u}}(W_{u}^{c_{u}}-1)+W_{u}^{c_{v}}(W_{v}^{c_{v}}-1)\leq
0$

If $Z_{v,:}=Z_{u,:}$, i.e., $c_{v}=c_{u}$, we have

$\displaystyle(ZZ^{T})_{v,u}=1$
$\displaystyle(\hat{A}ZZ^{T}\hat{A}^{T})_{v,u}=\sum\limits_{c=1}^{C}W_{v}^{c}W_{u}^{c}$
$\displaystyle(\hat{A}ZZ^{T})_{v,u}=W_{v}^{c_{v}}$
$\displaystyle(ZZ^{T}\hat{A}^{T})_{v,u}=(\hat{A}ZZ^{T})_{u,v}=W_{u}^{c_{u}}=W_{u}^{c_{v}}$

Then, from equation 19 it follows that

$\displaystyle S(I-\hat{A},Z)_{v,u}$
$\displaystyle=1+\sum\limits_{c=1}^{C}W_{v}^{c}W_{u}^{c}-W_{v}^{c_{v}}-W_{u}^{c_{v}}$
$\displaystyle=\sum\limits_{c=1,c\neq
c_{v}}^{C}W_{v}^{c}W_{u}^{c}+1+W_{v}^{c_{v}}W_{u}^{c_{v}}-W_{v}^{c_{v}}-W_{u}^{c_{v}}$
$\displaystyle=\sum\limits_{c=1,c\neq
c_{v}}^{C}W_{v}^{c}W_{u}^{c}+(1-W_{v}^{c_{v}})(1-W_{u}^{c_{v}})\geq 0$

Thus, if $C=2$, for any $v\in\mathcal{V}$, if $Z_{u,:}\neq Z_{v,:}$, we have
$S(I-\hat{A},Z)_{v,u}\leq 0$; if $Z_{u,:}=Z_{v,:}$, we have
$S(I-\hat{A},Z)_{v,u}\geq 0$. Apparently, the two conditions in equation 10
are satisfied. Thus $v$ is diversification distinguishable and
$\mathrm{DD}_{\hat{A},X}(\mathcal{G})=1$. The theorem is proved. ∎

##  Appendix H Discussion of the Limitations of Diversification Operation

Figure 13: Example of the case (the area in black box) that HP filter does not
work well for harmful heterophily

From the black box area of $S(I-\hat{A},X)$ in the example in Figure 13 we can
see that nodes in class 1 and 4 assign non-negative weights to each other
although there is no edge between them; nodes in class 2 and 3 assign non-
negative weights to each other as well. This is because the surrounding
differences of class 1 are similar as class 4, so are class 2 and 3. In real-
world applications, when nodes in several small clusters connect to a large
cluster, the surrounding differences of the nodes in the small clusters will
become similar. In such case, HP filter are not able to distinguish the nodes
from different small clusters.

##  Appendix I The Similarity, Homophily and
$\mathrm{DD}_{\hat{A},X}(\mathcal{G})$ Metrics and Their Estimations

Firstly, we would like to clarify that, for each curve in the synthetic
experiments, the node features are fixed and we only change the homophily
values. But in real-world tasks, different datasets have different features
and aggregated features. Thus, to get more instructive information for
different datasets and compare them, we need to consider more metrics, e.g.
feature-label consistency and aggregated-feature-label consistency. With the
similarity score of the features $S_{\text{agg}}\left(S(I,X)\right)$ and
aggregated features $S_{\text{agg}}\left(S(\hat{A},X)\right)$ listed in Table
15, our methods open up a new perspective on analyzing and comparing the
performance of graph-agnostic models and graph-aware models in real-world
tasks. Here are 2 examples.

#### Example 1:

People observe that GCN (graph-aware model) underperforms MLP-2 (graph-
agnostic model) on Cornell, Wisconsin, Texas, Film and people commonly believe
that the bad graph structure (low
$H_{\text{edge}},H_{\text{node}},H_{\text{class}}$ values) is the reason for
performance degradation. But based on the high aggregation homophily values,
the graph structure inconsistency is not the main cause of the performance
degradation. And from Table 15 we can see that the
$S_{\text{agg}}\left(S(\hat{A},X)\right)$ for those 4 datasets are lower than
their corresponding $S_{\text{agg}}\left(S(I,X)\right)$, which implies that it
is the aggregated-feature-label inconsistency that causes the performance
degradation, i.e. the aggregation step actually decrease the quality of node
features rather than making them more distinguishable.

For the rest 5 datasets Chameleon, Squirrel, Cora, Citeseer, PubMed, we all
have $S_{\text{agg}}\left(S(\hat{A},X)\right)$ larger than
$S_{\text{agg}}\left(S(I,X)\right)$ except PubMed, which means the aggregated
features have higher quality than raw features. We can see that the proposed
metrics are much more instructive than the existing ones.

#### Example 2:

According to $H_{\text{edge}},H_{\text{node}},H_{\text{class}}$, the value for
Chameleon, and Squirrel are extremely low indicating graph structure are bad
for GNNs. But on contrary, GCN outperforms MLP-2 on those 2 datasets.
Traditional homophily metrics fail to explain such phenomenon but our method
can give an explanation from different angles: For Chameleon, its modified
aggregation homophily is not low and its
$S_{\text{agg}}\left(S(\hat{A},X)\right)$ is higher than its
$S_{\text{agg}}\left(S(I,X)\right)$, which means its graph-label consistency
together with aggregated-feature-label consistency help the graph-aware model
obtain the performance gain; for Squirrel, its modified aggregation homophily
is low but its $S_{\text{agg}}\left(S(\hat{A},X)\right)$ is higher than its
$S_{\text{agg}}\left(S(I,X)\right)$, which means although its graph-label
consistency is bad, the aggregated-feature-label consistency is the key factor
to help the graph-aware model perform better.

We also need to point out that (modified) aggregation similarity score,
$S_{\text{agg}}\left(S(\hat{A},X)\right)$ and
$S_{\text{agg}}\left(S(I,X)\right)$ are not deciding values because they do
not consider the nonlinear structure in the features. In practice, a low score
does not tell us the GNN models will definitely perform bad.

Table 15: Additional metrics and their estimations with only training labels (mean $\pm$ std) | Cornell | Wisconsin | Texas | Film | Chameleon | Squirrel | Cora | CiteSeer | PubMed
---|---|---|---|---|---|---|---|---|---
$H_{\text{agg}}(\mathcal{G})$ | 0.9016 | 0.8884 | 0.847 | 0.8411 | 0.805 | 0.6783 | 0.9952 | 0.9913 | 0.9716
$S_{\text{agg}}\left(S(\hat{A},X)\right)$ | 0.8251 | 0.7769 | 0.6557 | 0.5118 | 0.8292 | 0.7216 | 0.9439 | 0.9393 | 0.8623
$S_{\text{agg}}\left(S(I,X)\right)$ | 0.9672 | 0.8287 | 0.9672 | 0.5405 | 0.7931 | 0.701 | 0.9103 | 0.9315 | 0.8823
$DD_{\hat{A},X}(\mathcal{G})$ | 0.3497 | 0.6096 | 0.459 | 0.3279 | 0.3109 | 0.2711 | 0.2681 | 0.4124 | 0.1889
$\hat{H}_{\text{agg}}(\mathcal{G})$ |  0.9046 $\pm$ 0.0282 |  0.9147 $\pm$ 0.0260 |  0.8596 $\pm$ 0.0299 |  0.8451 $\pm$ 0.0041 |  0.8041 $\pm$ 0.0078 |  0.6788 $\pm$ 0.0077 |  0.9959 $\pm$ 0.0011 |  0.9907 $\pm$ 0.0015 |  0.9724 $\pm$ 0.0015
$\hat{S}_{\text{agg}}\left(S(\hat{A},X)\right)$ |  0.8266 $\pm$ 0.0526 |  0.8280 $\pm$ 0.0351 |  0.6835 $\pm$ 0.0498 |  0.5345 $\pm$ 0.0421 |  0.8433 $\pm$ 0.0070 |  0.7352 $\pm$ 0.0132 |  0.9487 $\pm$ 0.0023 |  0.9451 $\pm$ 0.0038 |  0.8626 $\pm$ 0.0021
$\hat{S}_{\text{agg}}\left(S(I,X)\right)$ |  0.9752 $\pm$ 0.0174 |  0.8680 $\pm$ 0.0270 |  0.9661 $\pm$ 0.0336 |  0.5438 $\pm$ 0.0184 |  0.8257 $\pm$ 0.0050 |  0.7472 $\pm$ 0.0089 |  0.9204 $\pm$ 0.0044 |  0.9441 $\pm$ 0.0036 |  0.8835 $\pm$ 0.0019
$\hat{DD}_{\hat{A},X}(\mathcal{G})$ |  0.3936 $\pm$ 0.0663 |  0.6073 $\pm$ 0.0436 |  0.4817 $\pm$ 0.0762 |  0.3300 $\pm$ 0.0136 |  0.3329 $\pm$ 0.0151 |  0.3021 $\pm$ 0.0101 |  0.3198 $\pm$ 0.0225 |  0.4424 $\pm$ 0.0136 |  0.1919 $\pm$ 0.0046

Furthermore, in most real-world applications, not all labels are available to
calculate the dataset statistics. Thus, we randomly split the data into
60%/20%/20% for training/validation/test, and only use the training labels for
the estimation of the statistics. We repeat each estimation for 10 times and
report the mean with standard deviation. The results are shown in table 15.

#### Analysis

From the reported results we can see that the estimations are accurate and the
errors are within the acceptable range, which means the proposed metrics and
similarity scores can be accurately estimated with a subset of labels and this
is important for real-world applications.

##  Appendix J A Detailed Explanation of the Differences Between ACM(II)-GNNs
and GPRGNN, FAGCN

Differences with GPRGNN [8]:

  * •

_GPRGNN does not feed distinct node-wise feature transformation to different
"multi-scale channels"_

We first rewrite GPRGNN as

$\mathbf{Z}=\sum\limits_{k=0}^{K}\gamma_{k}\mathbf{H}^{(k)}=\sum\limits_{k=0}^{K}\gamma_{k}I\mathbf{H}^{(k)}=\sum\limits_{k=0}^{K}diag(\gamma_{k},\gamma_{k},\dots,\gamma_{k})\mathbf{H}^{(k)},\text{
where
}\mathbf{H}^{(k)}=\hat{A}_{\text{sym}}\mathbf{H}^{(k-1)},\mathbf{H}^{(0)}_{i:}=f_{\theta}(X_{i:}).$

From the above equation we can see that
$\mathbf{Z}=\sum\limits_{k=0}^{K}\gamma_{k}\hat{A}_{\text{sym}}^{k}f_{\theta}(X_{i:})$,
i.e., the node-wise feature transformation in GPRGNN is only learned by the
same $\theta$ for all the "multi-scale channels". But in the ACM framework,
different channels extract distinct information with different parameters
separately.

  * •

_GPRGNN does not have node-wise mixing mechanism._

There is no node-wise mixing in GPRGNN. The mixing mechanism in GPRGNN is
$\mathbf{Z}=\sum\limits_{k=0}^{K}diag(\gamma_{k},\gamma_{k},\dots,\gamma_{k})\mathbf{H}^{(k)}$,
i.e. for each "multi-scale channel $k$", all nodes share the same mixing
parameter $\gamma_{k}$. But in the ACM framework, the node-wise channel mixing
can be written as
$\mathbf{Z}=\sum\limits_{k=0}^{K}diag(\gamma_{k}^{1},\gamma_{k}^{2},\dots,\gamma_{k}^{N})\mathbf{H}^{(k)}$
where $K$ is the number of channels, $N$ is the number of nodes and
$\gamma_{k}^{i},i=1,\dots,N$ are the mixing weights that are learned by node
$i$ to mix channel $k$. ACM and ACMII allow GNNs to learn more diverse mixing
parameters in diagonal than GPRGNN and thus, have stronger expressive power
than GPRGNN.

Differences with FAGCN [4]:

  * •

_The targets of node-wise operations in ACM (channel mixing) and FAGCN
(negative message passing) are different._

Instead of using a fixed low-pass filter $\hat{A}$, FAGCN tries to learn a
more powerful aggregator $\hat{A}^{\prime}$ based on $\hat{A}$ by allowing
negative message passing. The node-wise operation in FAGCN is similar to GAT
[3] which is trying to modify the node-wise filtering (message passing)
process, i.e. for each node $i$, it assigns different weights
$\alpha_{ij}\in[-1,1]$ to different neighborhood nodes (equation 7 in FAGCN
paper). The goal of this node-wise operation in FAGCN is to learn a new filter
during the filtering process node-wisely. But in ACM, the node-wise operation
is to mix the filtered information from each channel which is processed by
different fixed filters. The targets of two the node-wise operations are
actually different things.

  * •

_FAGCN does not learn distinct information from different "channels". FAGCN
only uses simple addition to mix information instead of node-wise channel
mixing mechanism_

The learned filter $\hat{A}^{\prime}$ can be decomposed as
$\hat{A}^{\prime}=\hat{A}_{1}^{\prime}+(-\hat{A}_{2}^{\prime})$, where
$\hat{A}_{1}^{\prime}$ and $-\hat{A}_{2}^{\prime}$ represent positive and
negative edge (propagation) information, respectively. But FAGCN does not feed
distinct information to $\hat{A}_{1}^{\prime}$ and $-\hat{A}_{2}^{\prime}$.
Moreover, the aggregated $\hat{A}_{1}^{\prime}X$ and "diversified" information
$(-\hat{A}_{2}^{\prime})X$ are simply added together instead of using any
node-wise mixing mechanism. In ACM, we learn distinct information separately
in each channel with different parameters and add them adaptively and node-
wisely instead of just adding them together. In section 6.1, the ablation
study has empirically shown that node-wise adaptive channel mixing is better
than simple addition.