Date of publication xxxx 00, 0000, date of current version xxxx 00, 0000.
10.1109/ACCESS.2017.DOI

# Improving Performance of Object Detection using the Mechanisms of Visual
Recognition in Humans

AMIR GHASEMI  NASRIN BAYAT  FATEMEH MOTTAGHIAN  AKRAM BAYAT1  The Berkeley
Institute for Data Science, Berkeley, California, USA

###### Abstract

Object recognition systems are usually trained and evaluated on high
resolution images. However, in real world applications, it is common that the
images have low resolutions or have small sizes. In this study, we first track
the performance of the state-of-the-art deep object recognition network,
Faster-RCNN, as a function of image resolution. The results reveals negative
effects of low resolution images on recognition performance. They also show
that different spatial frequencies convey different information about the
objects in recognition process. It means multi-resolution recognition system
can provides better insight into optimal selection of features that results in
better recognition of objects. This is similar to the mechanisms of the human
visual systems that are able to implement multi-scale representation of a
visual scene simultaneously. Then, we propose a multi-resolution object
recognition framework rather than a single-resolution network. The proposed
framework is evaluated on the PASCAL VOC2007 database. The experimental
results show the performance of our adapted multi-resolution Faster-RCNN
framework outperforms the single-resolution Faster-RCNN on input images with
various resolutions with an increase in the mean Average Precision (mAP) of
9.14% across all resolutions and 1.2% on the full-spectrum images.
Furthermore, the proposed model yields robustness of the performance over a
wide range of spatial frequencies.

###### Index Terms:

Computer Vision, Deep Neural Network, Object Recognition, Multi-Resolution,
Faster-RCNN, Human Visual System

=-15pt

##  I Introduction

Recent advances in deep neural networks (DNN) [1, 2, 3, 4] and access to very
large datasets with million annotated data especially for computer vision
applications have led to state-of-the-art results in many problem domains such
as object detection and scene classification [5, 6, 7]. For example, Faster-
RCNN network [8] achieved the impressive results in recognition and
localization of objects in natural scenes or GoogleNet [9] reached
approximately to the human performance in classification of the ImageNet
database [10].

Despite the significant achievements, a major drawback of the current deep
neural networks for visual recognition is that they have been trained and
evaluated on high quality images in which their performances drop
significantly in classification of the low resolution images [11], [12].

in other words, previous works only focus on full spectrum image resolutions
when training their networks, but the variety of real-world applications, from
moving objects to small size images, often demand different constraints. Given
the real-world resource constraints such as low resolution and small size
images, recognition efficiency and performance becomes increasingly important
for object detection. However to achieve better efficiency, accuracy usually
is scarifies. This paper aims to tackle this problem by systematically
studying the performance of the object recognition networks (e.g., Faster-
RCNN) under the various resolutions of input images. Then, we propose a method
based on the mechanism of the human visual system that produces better and
robust performance in deep object detection networks with both higher accuracy
and better efficiency across a wide rang of image resolutions. To evaluate the
performance of our proposed method for object recognition, we choose the
Faster-RCNN network [8] as one of the best existing models in terms of the
accuracy on PASCAL VOC [13] image database.

##  II Related Work

Object Detection in Human Visual System - Visual perception in humans is a
process that human acquire knowledge about their environment. This process is
initiated when surrounding light enters the eye and induces electrical signals
subsequently processed within the brain where an image is formed.

A large volume of studies has shown that human visual system has the ability
to adapt to changes in environment in different ways, in which each adjustment
may need different mechanisms [14, 15, 16, 17]. For example adaptation to
color encompasses different adjustments including sensitivity changes in the
cones.

Human visual system has also spatial adaptations. As an example, tilt
aftereffects can be deduced with both real and subjective contours, with
asymmetries between them which encourages adaptation at different cortical
sites [18].

Visual objects in the real world are observed in contextual scenes which are
usually relevant from physical and semantic perspective. With regard to
blurriness, Bar et al. [19] deployed a blurred, low frequency representation
of a scene and showed that human visual system is able to determine ambiguous
objects.
Object Detection in Computer Vision - It deals with discovering instances of
semantic objects of a certain class (e.g. buildings, cars, or humans) in
images and videos. Most traditional approaches for object detection used well-
established computer vision methods which relies on extracting feature
descriptors (e.g., SIFT, SURF, BRIEF, etc.)[20, 21, 22]. However, with the
emerge of deep neural networks (in particular, convolutional neural network
[9]) and its remarkable success in computer vision, the majority of recent
works in object detection for digital images and videos have shifted towards
using them as the primary technique [23]. The state-of-the-art technique using
DNN can be categorized into two main types: one-stage methods and two stage-
methods. One-stage methods prioritize inference speed (e.g., YOLO [24], SSD
[25] and RetinaNet [26]). Two-stage methods prioritize detection accuracy
(e.g., Faster R-CNN [8], Mask R-CNN [27] and Cascade R-CNN [28]).

In this study, we focus on improving detection accuracy and efficiency in
detecting objects in low resolution images and videos. As said before, the
existing neural networks are generally trained and tested on high quality
images, in which when they are fed in with low quality images, their
performance in detecting and recognizing objects reduces remarkably [29].
However, in real life, there are many cases that images have low resolution.
To solve this issue, motivated by the capability of human visual system in
adapting to different range of resolution, we propose a multi-resolution
method which improves the performance of the model which it is fed in with
blurry images.

##  III Tracking Object recognition network performance

In this section, we explain our methodology to track performance of the state
of the art deep object recognition network, faster-RCNN with various
resolution levels along with notation and problem formulation.

###  III-A Model Architecture

We deploy Faster-RCNN framework for object detection and localization. The
Faster-RCNN uses Region Proposal Network (RPN) and an object detection network
that share convolutional layers for fast testing. The baseline network is
VGG-16 and its Conv 5-3 features are used for region proposal. We adapted the
Faster-RCNN based on the publicly available code in [30] and implemented it
with a few modifications in TensorFlow to evaluate the performance of the
network on 4952 images of the PASCAL VOC2007 test dataset with full resolution
(full spectrum in the frequency domain).

###  III-B Notation and Problem Formulation

As said before, we evaluate the performance of the Faster-RCNN network on the
PASCAL VOC2007 image database under multiple resolutions. For this purpose, we
create a set of image databases whose resolutions vary systematically from
extremely coarse to very fine. This is performed by applying the two-
dimensional Gaussian low pass filter in various cut off frequencies to the
PASCAL VOC2007 image database in the frequency domain. The results of this
process resemble blurring of an image to reduce the details of high frequency
components of that image in multiple levels. To simplify, instead of applying
a two dimensional (2D) Gaussian function to each pixel of an image which is
equivalent to convolving a 2D Gaussian with the image, we apply the product of
their individual Fourier transforms. We then re-transform the resulting
product into the spatial domain to obtain the image in the desired resolution
($I_{f_{c}}$).

Attenuating frequencies using low pass Gaussian filters [31] results in a
smoother image in the spatial domain. This process is formalized in the
following equations:

$\hat{F}_{f_{c}}(u,v)=F(u,v)H_{f_{c}}(u,v),f_{min}<f_{c}<f_{max}$ (1)
$H_{f_{c}}(u,v)=e^{-\frac{u^{2}+v^{2}}{2f_{c}^{2}}}$ (2)
$I_{f_{c}}=f^{-1}\left[\hat{\mathcal{F}}_{f_{c}}(u,v)\right]$ (3)

where $F(u,v)$ is the Fourier transform of the full-spectrum image $I$ and
$u,v$ are representative of a particular spatial frequency contained in the
spatial domain of image $I$. For instance, $F(0,0)$ represents the DC-
component of the image which corresponds to the average brightness.
$H_{f_{c}}$ is the 2D Gaussian spatial filter with cut-off frequency of
$f_{c}$ ranging from $f_{min}$ to $f_{max}$ which is defined systematically
between the center and the edge of the Fourier image, $F$ , as follows:

$f_{c}=c.\frac{w}{20}$ (4)

In this way, for a given image $I_{w\times h}$:

$f_{min}=\frac{S}{20},f_{max}=S,S=max(w,h)$ (5)

By doing so, we systematically create 20 image databases from the PASCAL
VOC2007 database in twenty-scale resolutions, namely PASCAL VOC2007- $R_{1}$,
. . . , PASCAL VOC2007- $R_{20}$.

Figure 1: The performance of multi-resolution Faster- RCNN obtained from the
combination of 5 models on 5 resolution levels ($R_{5},R_{10},R_{18},R_{20}$,
and Full-spectrum). All models have been evaluated on multi-resolution test
databases ($R_{1},...,R_{20}$)

##  IV Performance V.S. Resolutions

However, the state of the art object detectors are trained and tested on high
resolution images but a most important question is how we can have detectors
that give us the best balance of resolution and accuracy for different
application needed. In this section, we evaluate the comparison of accuracy
v.s. resolution tradeoff.

Dataset. The PASCAL Visual Object Classes 2007 (VOC2007) Dataset is considered
as our image database that contains 9963 images that are categorized into 20
object classes as explained in the previous section. The data has been split
into 5011 images for training and validation and 4952 test images. The
distribution of images and objects by class is approximately equal across the
training, validation and test datasets [32].
Figure 2 illustrates examples of an image from PASCAL VOC2007 database in the
multiple levels of spatial frequencies ranging from low to high frequencies.

Figure 2: Top row from left to right. Resolutions: full-spectrum, $R_{20}$
blurred with ($f_{c}=20\textperiodcentered\frac{w}{20})$, $R_{18}$: blurred
with ($f_{c}=18\textperiodcentered\frac{w}{20})$. Bottom row from left to
right. Resolutions: $R_{8}$ blurred with
($f_{c}=8\textperiodcentered\frac{w}{20})$, $R_{5}$: blurred with
($f_{c}=5\textperiodcentered\frac{w}{20})$, $R_{1}$: blurred with
($f_{c}=1\textperiodcentered\frac{w}{20})$

###  IV-A Performance Evaluation of the Faster-RCNN on Different Resolutions

To track the performance in the object detection, our performance evaluation
metric is the mean Average Precision (mAP) which is a very common and popular
performance measure in object detection tasks. The Average Precision is
defined as the fraction of the images with a relevant detected object among
all images with detected objects. In other words, the average precision is the
area under the precision-recall curve for each categories of objects. The mean
average precision is computed by taking the mean of the average precision for
all category of objects [13, 33].

Figure 3: Illustration of the performance of Faster- RCNN network on
recognition of objects on the PASCAL VOC 2007 test dataset (4952 images) in
multiple resolutions.

Figure 3 shows the Faster-RCNN results of detection when tested on the PASCAL
VOC2007 test data in various levels of resolution ($R_{1},...,R_{20}$) as
explained in the previous section. The results reveal that the performance of
the Full-spectrum Model drops off quickly for low resolution images compared
with the high resolution and full-spectrum images. This indicates that the
representations that are learned for the object recognition in a deep neural
network highly depend to the information from all spatial frequencies
simultaneously. Hence, the lack of information from the specific scale
negatively influences the recognition performance. However, the human visual
system can detect objects in most of the resolution levels since the human
brain provides representations of objects and scenes at multiple scales so
that it can still interpret the scenes and objects even in a single level
representation.

TABLE I: Performance comparison (mAP) of Faster- RCNN models trained on different resolutions for different resolution test cases created from PASCAL VOC2007 database Database-Resolution |  Full-spectrum Model mAP(%) |  $\frac{20}{20}$ -Model mAP(%) |  $\frac{18}{20}$ -Model mAP(%) |  $\frac{10}{20}$ -Model mAP(%) |  $\frac{5}{20}$ -Model mAP(%)
---|---|---|---|---|---
Full-spectrum |  68.1% |  68.7% |  68.4% |  67.6% |  61.6%
$R_{20}$ |  63.9% |  67.2% |  67.3% |  66.6% |  61.7%
$R_{18}$ |  63.7% |  67.5% |  67.3% |  66.7% |  62.1%
$R_{10}$ |  60.1% |  64.9% |  65.3% |  65.9% |  63.5%
$R_{5}$ |  45.5% |  52.3% |  51.2% |  57.0% |  61.3%

###  IV-B Deploying a Multi-Resolution Faster-RCNN

We propose a Multi-Resolution Faster-RCNN model that is made up of 5 end-to-
end trained models on various resolution levels. A combination rule is applied
during the test scheme such that a given image is passed through all 5 models
and the best object recognition results are derived based on the combination
rule that will be discussed shortly.

The combinational rule is adopted as an external module independent of the
training scheme. To detect objects in a given input image to the Multi-
Resolution Faster- RCNN model, all detections are collected from each of the
five individual models. Each detected object is provided in the form of a
bounding box and a score indicating the predicted probability of that bounding
box belonging to an object class. The number of detections in each model may
vary between 0 to 300, depending on the input image. Thus it is expected to
have between 1 to 1500 proposed objects (presented as bounding box
coordinates, predicted class score, and object class) for the combination of
all five models. However, many of these bounding boxes highly overlap. For
this, non-maximum suppression is used on the collection of all detected
bounding boxes to reduce the redundancy. The Intersection-over-Union (IoU)
threshold for non- maximum suppression is adopted at 0.7 to remove the
redundant bounding boxes [8]. All remaining objects are proposed as the
detection results of the Multi-Resolution Faster-RCNN model. Figure 4
illustrates the detection scheme.

For evaluation of the the Multi-Resolution Faster-RCNN model, the process is
implemented using the five models that were trained on PASCAL VOC2007
training/validation data (5K) in five different resolutions. Then, 20 test
databases in 20 levels of resolutions were generated from the PASCAL VOC2007
test data (5k). For each test database (corresponding to a certain
resolution), the results of object detections from 5 models are obtained. Non-
maximum suppression is adapted both based on the IoU threshold value of 0.7 as
well as highest overlap with the ground truth bounding boxes. The detection
results for five models and the Multi-resolution Faster-RCNN on 20 test
databases (PASCAL VOC2007-$R_{1,...,20}$) are shown in Figure 1. The combined
model, Multi-Resolution Faster-RCNN, outperforms all the models in detecting
images in all ranges of resolutions. The results indicate the robustness,
efficiency, and higher performance of the Multi-Resolution Faster-RCNN
regardless of the resolution of the input image in comparison to the Faster-
RCNN for object recognition.

Figure 4: The detection scheme in the Multi-Resolution Faster-RCNN.

##  V Conclusion and Future Work

Inspired by the capability of human visual system for adapting to different
resolution of images, in this work, we developed a multi-resolution deep
object recognition framework which solves the issue of significant drop in the
detection accuracy that happens for deep neural networks when trained and
evaluated on different resolutions. This indicates that the representations
that are learned for the object recognition in deep neural network highly
depend to the information from all spatial frequencies simultaneously. Hence,
the lack of information from the certain scale negatively influence the
recognition performance. To address this, we propose a Multi-Resolution
Faster-RCNN model that is made up of 5 end to end trained models on various
resolution levels. The combination rule is applied during the test scheme such
that a given image is passed through all 5 models and the best object
recognition results are derived based on the combination rule. Our experiments
show that the Multi-Resolution Faster-RCNN outperforms the original Faster-
RCNN object detector in detecting images in all ranges of resolutions. The
results indicate the robustness, efficiency, and higher performance of the
Multi-Resolution Faster-RCNN regardless of the resolution of the input image
than Faster-RCNN for object recognition.

## References

  * [1] N. Bayat and J.-H. Park, “Particle swarm optimization based demand response using artificial neural network based load prediction,” in _2022 North American Power Symposium (NAPS)_ , 2022, pp. 1–5.
  * [2] A. Bayat and M. Pomplun, “Deriving high-level scene descriptions from deep scene cnn features,” in _2017 Seventh International Conference on Image Processing Theory, Tools and Applications (IPTA)_. IEEE, 2017, pp. 1–6.
  * [3] A. Bayat, C. Anderson, and P. Shah, “Automated end-to-end deep learning framework for classification and tumor localization from native non-stained pathology images,” in _Medical Imaging 2021: Image Processing_ , vol. 11596\. SPIE, 2021, pp. 43–54.
  * [4] A. Bayat, H. Do Koh, A. Kumar Nand, M. Pereira, and M. Pomplun, “Scene grammar in human and machine recognition of objects and scenes,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops_ , 2018, pp. 1992–1999.
  * [5] B. Zhou, A. Lapedriza, J. Xiao, A. Torralba, and A. Oliva, “Learning deep features for scene recognition using places database,” _Advances in neural information processing systems_ , vol. 27, pp. 487–495, 2014.
  * [6] R. Girshick, J. Donahue, T. Darrell, and J. Malik, “Rich feature hierarchies for accurate object detection and semantic segmentation,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2014, pp. 580–587.
  * [7] N. Bayat, E. Rastegari, and Q. Li, “Human gait recognition using bag of words feature representation method,” _arXiv preprint arXiv:2203.13317_ , 2022\.
  * [8] S. Ren, K. He, R. Girshick, and J. Sun, “Faster r-cnn: Towards real-time object detection with region proposal networks,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 39, no. 6, pp. 1137–1149, 2016\.
  * [9] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich, “Going deeper with convolutions,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2015, pp. 1–9.
  * [10] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in _2009 IEEE conference on computer vision and pattern recognition_. Ieee, 2009, pp. 248–255.
  * [11] S. Dodge and L. Karam, “Understanding how image quality affects deep neural networks,” in _2016 eighth international conference on quality of multimedia experience (QoMEX)_. IEEE, 2016, pp. 1–6.
  * [12] J.-H. Kim, S. Kwon, J. Fu, and J.-H. Park, “Hair follicle classification and hair loss severity estimation using mask r-cnn,” _Journal of Imaging_ , vol. 8, no. 10, p. 283, 2022.
  * [13] M. Everingham, L. Van Gool, C. K. Williams, J. Winn, and A. Zisserman, “The pascal visual object classes (voc) challenge,” _International journal of computer vision_ , vol. 88, no. 2, pp. 303–338, 2010.
  * [14] M. A. Webster, “Visual adaptation,” _Annual review of vision science_ , vol. 1, pp. 547–567, 2015.
  * [15] D. P. McGovern, N. W. Roach, and B. S. Webb, “Perceptual learning reconfigures the effects of visual adaptation,” _Journal of Neuroscience_ , vol. 32, no. 39, pp. 13 621–13 629, 2012.
  * [16] H. Harris, M. Gliksberg, and D. Sagi, “Generalized perceptual learning in the absence of sensory adaptation,” _Current biology_ , vol. 22, no. 19, pp. 1813–1817, 2012.
  * [17] M. A. Webster, “Adaptation and visual coding,” _Journal of vision_ , vol. 11, no. 5, pp. 3–3, 2011.
  * [18] C. M. Howard and M. A. Webster, “Mccollough effect,” _Scholarpedia_ , vol. 6, no. 2, p. 8175, 2011.
  * [19] M. Bar, “Visual objects in context,” _Nature Reviews Neuroscience_ , vol. 5, no. 8, pp. 617–629, 2004.
  * [20] D. G. Lowe, “Object recognition from local scale-invariant features,” in _Proceedings of the seventh IEEE international conference on computer vision_ , vol. 2. Ieee, 1999, pp. 1150–1157.
  * [21] H. Bay, T. Tuytelaars, and L. Van Gool, “Surf: Speeded up robust features,” in _European conference on computer vision_. Springer, 2006, pp. 404–417.
  * [22] M. Calonder, V. Lepetit, C. Strecha, and P. Fua, “Brief: Binary robust independent elementary features,” in _European conference on computer vision_. Springer, 2010, pp. 778–792.
  * [23] N. Westlake, H. Cai, and P. Hall, “Detecting people in artwork with cnns,” in _European Conference on Computer Vision_. Springer, 2016, pp. 825–841.
  * [24] J. Redmon, S. Divvala, R. Girshick, and A. Farhadi, “You only look once: Unified, real-time object detection,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 779–788.
  * [25] W. Liu, D. Anguelov, D. Erhan, C. Szegedy, S. Reed, C.-Y. Fu, and A. C. Berg, “Ssd: Single shot multibox detector,” in _European conference on computer vision_. Springer, 2016, pp. 21–37.
  * [26] T.-Y. Lin, P. Goyal, R. Girshick, K. He, and P. Dollár, “Focal loss for dense object detection,” in _Proceedings of the IEEE international conference on computer vision_ , 2017, pp. 2980–2988.
  * [27] K. He, G. Gkioxari, P. Dollár, and R. Girshick, “Mask r-cnn,” in _Proceedings of the IEEE international conference on computer vision_ , 2017, pp. 2961–2969.
  * [28] Z. Cai and N. Vasconcelos, “Cascade r-cnn: Delving into high quality object detection,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 6154–6162.
  * [29] S. P. Kannojia and G. Jaiswal, “Effects of varying resolution on performance of cnn based image classification: An experimental study,” _Int. J. Comput. Sci. Eng_ , vol. 6, no. 9, pp. 451–456, 2018.
  * [30] X. Chen and A. Gupta, “An implementation of faster rcnn with study for region sampling,” _arXiv preprint arXiv:1702.02138_ , 2017.
  * [31] N. Bayat, D. D. Davey, M. Coathup, and J.-H. Park, “White blood cell classification using multi-attention data augmentation and regularization,” _Big Data and Cognitive Computing_ , vol. 6, no. 4, p. 122, 2022.
  * [32] M. Everingham, L. Van Gool, C. K. Williams, J. Winn, and A. Zisserman, “The pascal visual object classes challenge 2007 (voc2007) results,” 2007.
  * [33] N. Bayat, E. Rastegari, and Q. Li, “Human gait recognition using bag of words feature-representation method, in: Tareq ahram and christianne falcão (eds) human factors and wearable technologies,” _AHFE (2022) International Conference.AHFE Open Access, vol 29. AHFE International, USA_ , 2022. [Online]. Available: http://doi.org/10.54941/ahfe1001481


# Pointspectrum: Equivariance Meets Laplacian Filtering for Graph
Representation Learning

Marinos Poiitis,1 Pavlos Sermpezis, 1 Athena Vakali 1

###### Abstract

Graph Representation Learning (GRL) has become essential for modern graph data
mining and learning tasks. GRL aims to capture the graph’s structural
information and exploit it in combination with node and edge attributes to
compute low-dimensional representations. While Graph Neural Networks (GNNs)
have been used in state-of-the-art GRL architectures, they have been shown to
suffer from over smoothing when many GNN layers need to be stacked. In a
different GRL approach, spectral methods based on graph filtering have emerged
addressing over smoothing; however, up to now, they employ traditional neural
networks that cannot efficiently exploit the structure of graph data.
Motivated by this, we propose PointSpectrum, a spectral method that
incorporates a set equivariant network to account for a graph’s structure.
PointSpectrum enhances the efficiency and expressiveness of spectral methods,
while it outperforms or competes with state-of-the-art GRL methods. Overall,
PointSpectrum addresses over smoothing by employing a graph filter and
captures a graph’s structure through set equivariance, lying on the
intersection of GNNs and spectral methods. Our findings are promising for the
benefits and applicability of this architectural shift for spectral methods
and GRL.

##  1 Introduction

Graphs are universal mathematical structures –usually accompanied by a
plethora of features– that are extensively used to describe real-world data in
various domains such as citation and social networks (Kipf and Welling 2016a;
Liu et al. 2019), recommender systems (Zhang and Chen 2019), or adversarial
attacks (Zhang and Zitnik 2020). Due to the complex structure of graphs,
traditional machine learning models are insufficient for addressing graph-
based tasks such as node and graph classification, link prediction and node
clustering. This necessity has given rise to Graph Representation Learning
(GRL) methods, which aim to capture the structure of input graph data and
produce meaningful low-dimensional representations.

A main track of GRL methods is based on Graph Neural Networks (GNNs). GNNs and
specifically Graph Convolutional Networks (GCN) (Kipf and Welling 2016a) have
advanced the research on GRL leading to outstanding performance as they
capture a node’s neighborhood influence. Nevertheless, each GNN layer
considers only the local one-hop node relations leading to unavoidably deep
layer stacking to efficiently account for the global graph information.
Notwithstanding, vanilla GNNs cannot be arbitrarily deep as they lead to over
smoothing and information loss (Xu et al. 2018; Zhao and Akoglu 2019; Chen et
al. 2020). To address over smoothing, spectral methods exploiting graph
filters have been introduced (Wang et al. 2019; Zhang et al. 2019). However,
so far, these methods have been used in conjunction with traditional neural
networks (e.g., MLPs or CNNs) that cannot efficiently exploit the set
equivariance property of graph data (i.e., equivariance to permutations in the
input data). In the graph domain there is no implicit data ordering, and thus
the existing spectral methods waste an important portion of their
computational capacity.

Contribution. In this work, we propose PointSpectrum, a GRL architecture that
bridges the gap between GNN-based and spectral GRL methods (Section 2).
PointSpectrum is based on Laplacian smoothing (used in spectral methods to
alleviate the problem of over-smoothing), while it maintains the set
equivariance property of GNN-based approaches.

Specifically, PointSpectrum is an unsupervised end-to-end trainable
architecture, consisting of the following components:

  * •

Input: a low-pass graph filter (Laplacian smoothing) is applied on the input
graph data that enables the computation of k-order graph convolution for
arbitrarily large k without over smoothing node features

  * •

Encoder: the input data are fed to a set equivariant network that generates
low-dimensional node embeddings

  * •

Decoder: a joint loss is employed to account for the reconstruction of the
input data and their better separation in the embedding space through a
clustering metric.

Figure 1: PointSpectrum architecture. Encoder is a pointNetST network
producing node embeddings in an equivariant manner, the pair-wise decoder
reconstructs input $\mathbf{\bar{X}}$ and last ClusterNet is employed to
better separate points in the embedding space.

To the best of our knowledge this is the first work that introduces set
equivariance in spectral GRL methods. Our experimental results (Section 3)
show that: (i) Using set equivariant networks can increase the robustness
(wrt. the model parameters) and efficiency (e.g., faster convergence,
expressiveness) of spectral methods. (ii) PointSpectrum presents high
performance in all benchmark tasks and datasets, outperforming or competing
with the state-of-the-art (detailed in Section 4). Overall, our findings
showcase a new direction for GRL: the combination of spectral methods with set
equivariance. Incorporating set equivariant networks in existing spectral
methods can be straightforward (e.g., replacing MLPs or CNNs), and our results
are promising for the efficiency of this approach.

##  2 Methodology

Definitions. We consider a non-directed attributed graph
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})$, where
$\mathcal{V}=\\{v_{1},v_{2},...,v_{n}\\}$ is the node set with
$|\mathcal{V}|=n$, $\mathcal{E}$ is the edge set, and
$\mathbf{X}=[\mathbf{x}_{1},\mathbf{x}_{2},\dots,\mathbf{x}_{n}]^{T}\in\mathbb{R}^{n\times
l}$ is the feature matrix consisting of feature vectors
$\mathbf{x}_{i}\in\mathbb{R}^{l},~{}\forall v_{i}\in\mathcal{V}$. The
structural information of graph $\mathcal{G}$ is represented by the adjacency
matrix $\mathbf{A}=\\{a_{ij}\\}\in\mathbb{R}_{\geq 0}^{n\times n}$.

Goals. The goal of GRL is to map nodes to low-dimensional embeddings, which
should preserve both the structural ($\mathbf{A}$) and contextual
($\mathbf{X}$) information of $\mathcal{G}$. We denote as
$\mathbf{Z}\in\mathbb{R}^{n\times l^{\prime}}$, with $l^{\prime}\ll l$, the
matrix with the node embeddings.

Approach overview. We propose a methodology to compute an embedding matrix
$\mathbf{Z}$, which combines structural and contextual information in a
twofold way: on one hand, it uses Laplacian smoothing (based on $\mathbf{A}$)
of the feature matrix $\mathbf{X}$ (Section 2.1) and, on the other hand, by
considering the node features as a set of points it exploits global
information using a permutation equivariant network architecture (Section
2.2). Last, we leverage node clustering as a boosting component that further
enhances performance by better separating nodes in the embedding space. The
entire architecture that brings these components together is presented in
Section 2.3.

###  2.1 Graph Convolution and Laplacian Smoothing

The most important notion in the prevalent GNN-based embedding methods, such
as GCN (Kipf and Welling 2016a), is that neighboring nodes should be similar
and hence their features should be smoother than non-neighboring nodes in the
graph manifold. However, these methods capture deeper connections by stacking
multiple layers, leading to deep architectures, which are known to overly
smooth the node features (Chen et al. 2020). Over smoothing occurs as each
layer repeatedly smooths the original features so as to account for the deeper
interactions. To address this problem, the domain of graph signal processing
has been used and in particular graph convolution by using Laplacian Smoothing
filters (Zhang et al. 2019; Cui et al. 2020).

Specifically, “spectral methods” in GRL use a smoothed feature matrix
$\mathbf{\bar{X}}$, instead of the original $\mathbf{X}$, which corresponds to
a k-th order graph convolution of $\mathbf{X}$:

$\mathbf{\bar{X}}=\mathbf{H^{k}}\mathbf{X}$ (1)

where matrix $\mathbf{H}\in\mathbb{R}^{n\times n}$ is the Laplacian Smoothing
filter (discussed below). The multiplication of feature matrix $\mathbf{X}$
with filter $\mathbf{H}$ corresponds to a 1-order graph convolution (or
1-order graph smoothing). Stacking $k$ filters together, i.e., $k$
multiplications with $\mathbf{H}$, leads to a $k$-order convolution as in Eq.
1. Thus, deep network interactions are captured by the power of filter
$\mathbf{H}$ instead of repeated convolutions of the input features and
therefore over smoothing is avoided.

The Laplacian Smoothing Filter, $\mathbf{H}$: The intuition behind k-order
convolution of spectral methods is the following: Each column of feature
matrix $\mathbf{X(:,i)}\in\mathbb{R}^{n}$ (i.e., the vector with the values of
all nodes for a single feature) can be considered as a graph signal. The
smoothness of a signal depicts the similarity between the graph nodes. Since
neighboring nodes should be similar, to capture this similarity, we would need
to construct a smooth signal based on $\mathbf{X(:,i)}$ that captures node
adjacency and takes into account the features of the most important
neighboring nodes. It can be shown (details in Appendix A.7) that the
Laplacian Smoothing filter $\mathbf{H}$ as defined in Eq. 2 (Taubin 1995) can
cancel high frequencies between neighboring nodes and preserve the low ones:

$\mathbf{H}=\mathbf{I}-\mu\mathbf{L}$ (2)

where $\mu\in\mathbb{R}$, $\mathbf{I}$ is the identity matrix and $\mathbf{L}$
is the graph Laplacian. The graph Laplacian is defined as
$\mathbf{L}=\mathbf{D}-\mathbf{A}$, where
$\mathbf{D}=diag(d_{1},d_{2},\dots,d_{n})\in\mathbb{R}^{n\times n}$ is the
degree matrix of $\mathbf{A}$, with $d_{i}=\sum_{v_{j}\in\mathcal{V}}a_{ij}$
being the degree of node $v_{i}$. In order for $\mathbf{H}$ to be low-pass,
$1-\mu\lambda$ should be a non-negative degressive function. (Cui et al. 2020)
showed that the optimal value of $\mu$ is $1/\lambda_{max}$, with
$\lambda_{max}$ denoting the largest eigenvalue of $\mathbf{L}$; in the
remainder, we use this value for $\mu$.

(a) Accuracy (Cora)

(b) ARI (Cora)

(c) NMI (Cora)

Figure 2: Accuracy, ARI and NMI metrics of the PointSpectrum with PointNetST,
MLP and CNN-based networks in the encoder solving the clustering task on the
Cora dataset. For all metrics, the mean value and standard deviation of 10
experiment runs are depicted. The set equivariant PointNetST achieves higher
performance and is more robust than the MLP and CNN variants, irrespective of
the convolution order.

Renormalization trick: In practice the renormalization trick (Kipf and Welling
2016a), i.e., adding self-loops in the graph, has been shown to improve
accuracy and shrink the graph spectral domain (Wu et al. 2019). Qualitatively,
this means that for every node the smoothing filter also considers its own
features alongside the ones from its neighbors. Thus, we perform the following
transformation: self-loops are added to the adjacency:
$\mathbf{\bar{A}}=\mathbf{I}+\mathbf{A}$; we then use the symmetric normalized
graph Laplacian
$\mathbf{\bar{L}_{sym}}=\mathbf{\bar{D}^{-\frac{1}{2}}}\mathbf{\bar{L}}\mathbf{\bar{D}^{-\frac{1}{2}}}$,
where $\mathbf{\bar{D}}$ and $\mathbf{\bar{L}}$ are the degree and Laplacian
matrices of $\mathbf{\bar{A}}$. Finally, the resulting Laplacian smoothing
filter becomes $\mathbf{H}=\mathbf{I}-k\mathbf{\bar{L}_{sym}}$.

###  2.2 Equivariance and PointNetST

Neural network architectures can approximate any continuous function $f$ given
sufficient capacity and expressive power (Sonoda and Murata 2017; Sannai,
Takai, and Cordonnier 2019; Yarotsky 2021); here, we denote a neural network
as a function $f:\mathbf{X}\mapsto Y$ operating on the feature matrix
$\mathbf{X}$ (and by extension on $\mathbf{\bar{X}}$).

Sets and permutation equivariance. Conventional neural networks such as
Multilayer Perceptrons (MLPs) or Convolutional Neural Networks (CNNs) act on
data where there is an implicit order (e.g., adjacent pixels in images).
However, graphs do not have any implicit order: nodes can be presented in
different order but the graph still maintains the same structure
(isomorphism). To this end, $\mathbf{X}$ can be seen as a set of points
$\mathbf{x}\in\mathbb{R}^{l}$, and $f$ as a function operating on a set.

###### Definition 1

A function $f:\mathbb{R}^{n\times l}\mapsto\mathbb{R}^{n\times l^{\prime}}$
acting on a set $\mathbf{X}\in\mathbb{R}^{n\times l}$ is _permutation
equivariant_ when $f(\sigma\cdot\mathbf{X})=\sigma\cdot f(\mathbf{X})$ for any
permutation $\sigma$ of the set $\mathbf{X}$.

In other words, a permutation equivariant function $f$ produces the same
output (e.g., embedding, label) for each set item (e.g., node) irrespective of
the order of the given data. This means that if a transformation (e.g., a
permutation of the input matrix’s rows) is applied to the input data, then the
same transformation should be applied to the model’s output as well.

Equivariance in GRL methods. Set equivariance is not captured by traditional
neural networks such as MLPs (or CNNs), which are mainly used in the “spectral
methods” in GRL (Zhang et al. 2019; Cui et al. 2020). More specifically,
(Zaheer et al. 2017) proved that a function $f$ is permutation equivariant iff
it can be decomposed in the form
$\rho(\sum_{\mathbf{x}\in\mathbf{X}}\phi(\mathbf{x}))$, where $\rho$ and
$\phi$ are suitable transformations. Also, each MLP or CNN layer can be seen
as a transformation $\phi$, and a deep network with $m$ such layers can be
expressed as $f(\mathbf{X})=\phi_{m}\circ\dots\circ\phi_{1}(\mathbf{X})$.
Hence, the necessary decomposition for permutation equivariance does not hold.
On the contrary, GNNs can capture not only permutation equivariance but also
graph connectivity, which makes them even more expressive. Nevertheless, as
mentioned earlier, this high expressiveness comes with oversmoothing problems.
In this work, we aim to bring the benefits of both approaches used in GRL: we
employ a set equivariant network that accounts for the graph structure
(through the matrix $\mathbf{\bar{X}}$) and avoids oversmoothing at the same
time (as discussed in Section 2.1). This property is crucial for this work’s
model prevalence over the traditional neural networks, as it will be shown in
Section 3.

(a) Loss (Cora)

(b) Reconstruction loss (Cora)

(c) Clustering loss (Cora)

Figure 3: Total loss, reconstruction loss and clustering loss of PointSpectrum
with PointNetST, MLP and CNN-based networks in the encoder solving the
clustering task on the Cora dataset (mean values over 10 runs). The set
equivariant PointNetST helps the model converge faster than the MLP and CNN
variants.

PointNetST. In this work, PointNetST (Segol and Lipman 2019) is employed as
the permutation equivariant neural network architecture. While different
choices can be made, such as a deep self-attention network (Wang et al. 2018)
or the constructions of (Keriven and Peyré 2019) and (Sannai, Takai, and
Cordonnier 2019), PointNetST is preferred as it is provably a universal
approximator over the space of equivariant functions (Segol and Lipman 2019)
and can be implemented as an arbitrarily deep neural network with the
following form:

$f(\mathbf{X})=\phi_{m}\circ\sigma\dots\circ\sigma\circ\phi_{1}(\mathbf{X})$
(3)

where $\sigma$ is a non-linearity such as ReLU and $\phi_{i}$, $i=1,...,m$, is
the DeepSet layer (Zaheer et al. 2017):

$\phi_{i}(\mathbf{X})=\mathbf{X}\mathbf{W}_{1}+\frac{1}{n}\mathbf{1}\mathbf{1}^{T}\mathbf{X}\mathbf{W}_{2}+\mathbf{1}\mathbf{w}$
(4)

with $\mathbf{W}_{1},\mathbf{W}_{2}\in\mathbb{R}^{l_{i}\times l_{i+1}}$ and
$\mathbf{w}\in\mathbb{R}^{l_{i+1}}$ being the layer’s parameters. Remark:
while Eq. 4 is a generic form of an equivariant transformation, it is noted
that PointNetST contains only a single layer with non-zero $\mathbf{W}_{2}$.

###  2.3 PointSpectrum

This work proposes PointSpectrum, an encoder-decoder architecture for GRL that
consists of the following main components: (i) Laplacian smoothing of the
feature matrix, (ii) PointNetST as the permutation equivariant neural network
of the encoder, and (iii) a clustering module alongside the decoder. A
schematic representation of PointSpectrum is depicted in Figure 1.

Input. The input $\mathbf{\bar{X}}$ of the encoder-decoder network is the
$k$-order graph convolution of node feature matrix $\mathbf{X}$, which is
computed using a Laplacian filter $\mathbf{H}$ as described in Section 2.1.
The larger the convolution order $k$, the deeper node-wise interactions the
model can capture; $k$ is a hyper-parameter of the model.

Encoder. The encoder is the permutation equivariant PointNetST, which
generates the node embeddings $\mathbf{Z}$, as described in Section 2.2. The
embeddings are fed to two individual modules: the decoder and the ClusterNet.

Decoder: The aim of the decoder is to reconstruct a pairwise similarity value
between the computed node embeddings based on $\mathbf{\bar{X}}$. Different
choices for the reconstruction loss function can be made (e.g. minimum squared
error (Wang et al. 2019) or noise-contrastive binary cross entropy (Veličković
et al. 2018)). However, as connectivity is incorporated in the smoothed
signal, we use a pairwise decoder and cross entropy with negative sampling as
the loss function:

$L_{r}=-\sum_{i\in\mathcal{V}}\left[\sum_{(i,j)\in\mathcal{E}}\log(\mathbf{z}_{i}\mathbf{z}_{j})+\sum_{k\in\mathcal{N}_{i}}\log(1-\mathbf{z}_{i}\mathbf{z}_{k})\right]$
(5)

where $\mathcal{N}_{i}$ are the negative samples (i.e., non-existing edges)
for node $i$.

ClusterNet is a differentiable clustering module, which learns to assign nodes
to clusters to better separate them in the embedding space (Wilder et al.
2019). ClusterNet learns a distribution of soft assignments $\mathbf{Q}$,
where $q_{ij}$ expresses the probability of node $i$ belonging to cluster $j$,
by optimizing KL-divergence loss function:

$L_{c}=KL(P||Q)=\sum_{i}\sum_{j}p_{ij}\cdot\log\frac{p_{ij}}{q_{ij}}$ (6)

where $\mathbf{P}$ is a target distribution (updated in every epoch or using
different intervals) that emphasizes the more “confident” assignments (Wang et
al. 2019):

$p_{ij}=\frac{q_{ij}^{2}/\sum_{i}q_{ij}}{\sum_{j}(q_{ij}^{2}/\sum_{i}q_{ij})}$
(7)

Having computed $\mathbf{Q}$, cluster centers can be extracted directly by
averaging the soft assignments for each cluster. Overall, PointSpectrum
optimizes the following joint loss of the Decoder and ClusterNet

$L=\alpha\cdot L_{r}+\beta\cdot L_{c}$ (8)

with $\alpha,\beta$ being hyper parameters that control the importance of each
component.

##  3 Experimental Results

In this section, we demonstrate the efficiency of PointSpectrum in benchmark
GRL datasets and tasks. We first present the datasets, the experimental setup,
and the baseline methods we compare against to (Section 3.1). Then, we provide
experimental evidence for the gains that are introduced by the equivariance
component of PointSpectrum over the traditional deep learning architectures in
terms of efficiency (Sections 3.2), complexity (Section 3.3) and robustness
(Section 3.4). Finally, we compare the performance of PointSpectrum against
baseline and state-of-the art methods in GRL (Section 3.5) and provide a
qualitative visual analysis (Section 3.6).

###  3.1 Datasets & experimental setup

Datasets. We evaluated the performance of PointSpectrum on three widely used
benchmark citation network datasets, namely Cora (McCallum et al. 2000),
Citeseer (Giles, Bollacker, and Lawrence 1998) and Pubmed (Namata et al.
2012). The statistics of these data sources are presented and further
discussed in Appendix A.1.

Method MLP CNN PointNetST Cora ACC NMI ARI F1 0.275 0.247 0.170 0.145 (0.583)
(0.379) (0.363) (0.484) 0.301 0.090 0.514 0.208 (0.571) (0.417) (0.346)
(0.489) 0.625 0.431 0.385 0.538 (0.715) (0.528) (0.493) (0.693) Citeseer ACC
NMI ARI F1 0.308 0.053 0.043 0.272 (0.445) (0.199) (0.172) (0.400) 0.362 0.098
0.091 0.314 (0.423) (0.197) (0.175) (0.395) 0.537 0.316 0.271 0.463 (0.703)
(0.430) (0.451) (0.613) Pubmed ACC NMI ARI F1 0.433 0.022 0.002 0.269 (0.638)
(0.210) (0.212) (0.639) 0.457 0.063 0.018 0.323 (0.684) (0.263) (0.298)
(0.673) 0.691 0.298 0.307 0.687 (0.710) (0.295) (0.329) (0.703)

Table 1: Clustering results based on the true labels. The input is randomly
permuted in every epoch during training. The reported metrics result from the
best clustering assignments of the original (not permuted) input. The results
in the parenthesis refer to the models’ performance when trained on the
original input. PointSpectrum can capture data permutations on which it has
not been explicitly trained, whereas the MLP/CNN variants perform poorly.

PointSpectrum setup. For all evaluation tasks, a PointSpectrum model is used
for the encoder with a single PointNetST layer of dimension $l=100$ (which is
also the embedding dimension). For the clusterNet module, centers are randomly
initialized and correspond to the number of distinct labels in each dataset.
Last, weights are initialized according to (He et al. 2015) (He
initialization). Details for the hyperparameter tuning are given in Appendix
A.2.

Baseline methods. We compare PointSpectrum to several baseline methods (see
details in Section 4), which we distinguish in four categories: (i) feature-
only (K-Means), (ii) traditional GRL (DeepWalk, DNGR, TADW), (iii) GNN-based
(VGAE, ARVGA - and their simpler derivatives - and DGI, GIC), and (iv)
Spectral (DAEGC, AGC, AGE). In Section 3.5, we compare against all these
methods on clustering, and only the most prevalent ones on link prediction.
Results are obtained directly from (Mavromatis and Karypis 2020); in
particular, for AGE, K-means is used as the clustering method (instead of
spectral clustering as in (Cui et al. 2020)) to enable a fair comparison. In
Sections 3.2–3.4, the reported results correspond to the node clustering task,
since it is the most natural task for PointSpectrum, considering its
architecture.

###  3.2 Efficiency of set equivariance

We investigate the efficiency of using a set equivariant network (PointNetST)
along with Laplacian smoothing ($\mathbf{\bar{X}}$), by comparing the
PointSpectrum architecture (Figure 1) against two variants with MLP and CNN
neural networks in the encoder. Figure 2 shows the results for the different
encoder types and different convolution orders ($k$) for the clustering task
on the Cora dataset. 111 The corresponding results on the Citeseer and Pubmed
datasets can be found in Appendix A.5; on Citeseer PointNetST performs even
better than on Cora, while on Pubmed it performs similarly to MLP/CNN variants
(due to the small number of features and simpler graph structure).

PointNetST achieves higher performance, is more robust (lower variance), and
has less fluctuations with respect to the convolution order than the MLP and
CNN variants.

This prevalence of PointNetST suggests that set equivariant networks are able
to capture richer information when combined with Laplacian smoothing, and
could be good candidates for replacing the conventional encoders of other
Spectral methods as well (e.g., DAEGC, AGC, AGE).

###  3.3 Set equivariance vs. training convergence

Set equivariant networks can offer multi-faceted benefits. As shown in (Zaheer
et al. 2017; Segol and Lipman 2019) and in the results of Section 3.2, they
can capture richer structural information compared to the traditional MLP/CNN
variants. In addition to these benefits, here we show that they also aid in
training efficiency and computation complexity. Figure 3 depicts the value of
the loss function during the model’s training for the original PointNetST and
the MLP/CNN variants. 222Similar findings hold for the Citeseer and Pubmed
datasets; see Appendix A.6

In both components of the loss function (reconstruction, clustering) and the
joint loss, PointNetST helps PointSpectrum to converge faster than the MLP/CNN
variants.

Remark: PointNetST achieves a lower loss value in overall (Figure 3(a)). While
the clustering loss is slightly lower for the MLP/CNN variants (Figure 3(c))
this difference is infinitesimal (second decimal point) compared to the
reconstruction loss term (Figure 3(b)).

Method K-Means DeepWalk DNGR TADW GAE/VGAE ARGA/ARVGA DGI GIC DAEGC AGC AGE
PointSpectrum (ours) Cora ACC NMI ARI F1 0.492 0.321 0.230 0.368 0.484 0.327
0.243 0.392 0.419 0.318 0.142 0.340 0.560 0.441 0.332 0.481 0.609 0.436 0.347
0.609 0.711 0.526 0.495 0.693 0.713 0.564 0.511 0.682 0.725 0.537 0.508 0.694
0.704 0.528 0.496 0.682 0.689 0.537 0.487 0.656 0.712 0.559 - 0.682 0.736
0.529 0.516 0.711 Citeseer ACC NMI ARI F1 0.540 0.305 0.279 0.409 0.337 0.088
0.092 0.270 0.326 0.180 0.044 0.300 0.455 0.291 0.228 0.414 0.408 0.176 0.124
0.372 0.581 0.338 0.301 0.525 0.688 0.444 0.450 0.657 0.696 0.453 0.465 0.654
0.672 0.397 0.410 0.636 0.670 0.411 0.419 0.625 0.569 0.348 - 0.544 0.703
0.430 0.451 0.613 Pubmed ACC NMI ARI F1 0.398 0.001 0.002 0.195 0.684 0.279
0.299 0.670 0.458 0.155 0.054 0.467 0.511 0.001 0.001 0.335 0.672 0.277 0.279
0.660 0.690 0.305 0.306 0.678 0.533 0.181 0.166 0.186 0.673 0.319 0.291 0.704
0.671 0.266 0.278 0.659 0.698 0.316 0.319 0.404 - - - - 0.776 0.375 0.444
0.768

Table 2: Clustering results based on the true labels. Horizontal lines
discriminate feature-only, traditional GRL, GNN-based and Spectral methods.
Underlined values indicate the best results among the spectral methods, and
bold values the best results among all methods.

###  3.4 Performance on permuted data

As already shown, set equivariance offers performance and computational
efficiency. In this section we focus on the main characteristic of set
equivariance: its robustness on permuted inputs (which can be considered as a
specific type of noisy/corrupted input data). To demonstrate this, we train
PointSpectrum by randomly permuting the rows of $\mathbf{\bar{X}}$ (input
data) in every epoch. Then, the trained model is evaluated on the original
$\mathbf{\bar{X}}$.

Table 1 presents the results of this experiment, as well as the initial
results without permuted data during training (in parentheses). PointNetST
achieves the highest performance, but more importantly, the drop in
performance due to the corrupted input is significantly smaller compared to
the drop in the MLP/CNN variants. This highlights that PointSpectrum can
capture data permutations on which it has not been explicitly trained (e.g.,
in case of graph isomorphism). On the contrary, the MLP/CNN variants perform
poorly on permuted data (see, e.g., the NMI/ARI metrics in the Citeseer and
Pubmed datasets).

###  3.5 Comparison against baselines

In this section, we compare PointSpectrum’s efficiency in clustering and link
prediction tasks against baseline and state-of-the-art methods.

We would like to stress that the main goal of this work is to introduce set
equivariance in Laplacian smoothing (Spectral) GRL methods, and demonstrate
the benefits it can bring. Hence, we do not extensively emphasize on the
hyperparameter optimization of PointSpectrum. Here, we compare its performance
against baselines for completeness and for demonstrating its efficiency
compared to the state-of-the-art in GRL. Nevertheless, the tested
PointSpectrum implementation still outperforms Spectral methods, and achieves
top or near top performance in the evaluation tasks.

Clustering: The goal in clustering is to group similar nodes into $m$ classes
based on the computed embeddings. Similar to related literature, the number of
classes is given, and in the evaluation the labels provided by the datasets
are used. In Table 2 we report the best PointSpectrum results out of 10
experiment runs for 4 metrics: Accuracy (ACC), Normalized Mutual Information
(NMI), Adjusted Randomized Index (ARI) and Macro-F1 score (F1).

Focusing first on the Spectral methods (bottom rows of Table 2), we see that
the overall PointSpectrum performance (i.e., for the majority of metrics and
datasets) is superior to Spectral methods. When compared to all GRL methods,
PointSpectrum achieves state-of-the-art performance on most metrics in the
Cora and Pubmed datasets, as well as on the accuracy metric in the Citeseer
dataset (in which the GNN-based models GIC and DGI perform best for the other
metrics).

Link prediction: In link prediction, some graphs edges are hidden to the model
during training and its goal is to predict these hidden interactions based on
the computed node embeddings. For this task $10\%$ of positive and negative
edges are used as test and $20\%$ as the validation set. Table 3 presents the
model performance on link prediction (mean value and standard deviation over
10 runs) as measured by the Area Under the Curve (AUC) and Average Precision
(AP) metrics.

PointSpectrum outperforms all baselines by a significant margin in Cora ($\sim
5.5\%$ ) and Pubmed ($\sim 1.5\%$) datasets, while in Citeseer it is the
second best method after GIC (with less than $1\%$ margin; also note that
PointSpectrum has much lower variance than GIC).

Method DeepWalk GAE/VGAE ARGA/ARVGA DGI GIC AGE PointSpectrum (ours) Cora AUC
AP $0.846\pm 0.001$ $0.885\pm 0.000$ $0.914\pm 0.001$ $0.926\pm 0.001$
$0.924\pm 0.000$ $0.932\pm 0.000$ $0.898\pm 0.08$ $0.897\pm 0.1$ $0.935\pm
0.06$ $0.933\pm 0.07$ $0.924\pm 0.000$ $0.932\pm 0.000$ $\mathbf{0.989\pm
0.000}$ $\mathbf{0.989\pm 0.001}$ Citeseer AUC AP $0.805\pm 0.002$ $0.850\pm
0.001$ $0.908\pm 0.002$ $0.920\pm 0.002$ $0.924\pm 0.000$ $0.930\pm 0.000$
$0.955\pm 0.1$ $0.957\pm 0.1$ $\mathbf{0.970\pm 0.05}$ $\mathbf{0.968\pm
0.05}$ $0.924\pm 0.000$ $0.930\pm 0.000$ $0.966\pm 0.000$ $0.961\pm 0.001$
Pubmed AUC AP $0.842\pm 0.000$ $0.878\pm 0.000$ $0.964\pm 0.000$ $0.965\pm
0.000$ $0.968\pm 0.000$ $0.971\pm 0.000$ $0.912\pm 0.06$ $0.922\pm 0.05$
$0.937\pm 0.03$ $0.935\pm 0.03$ $0.968\pm 0.000$ $0.971\pm 0.000$
$\mathbf{0.987\pm 0.001}$ $\mathbf{0.982\pm 0.002}$

Table 3: Link prediction performance. Area Under the Curve (AUC) and Average
Precision (AP) are reported. Best results on each dataset are shown in bold,
and second best in underlined.

###  3.6 Qualitative Analysis

We evaluate qualitatively PointSpectrum by visualizing the computed embeddings
using t-SNE (Van der Maaten and Hinton 2008) for the Cora dataset in Figure 4
(see Appendix A.4 for visualizations on the Citeseer and Pubmed datasets).

(a) Initial

(b) Intermediate

(c) Final

Figure 4: PointSpectrum’s training behavior on Cora dataset using t-SNE for
visualization. ClusterNet’s trainable centers are denoted as black ‘x’ marks.

On one hand, we observe that PointSpectrum separates well the nodes in the
embedding space as the training proceeds. On the other hand, the ClusterNet
component enables the PointSpectrum to learn the cluster centers as well
(denotes as ‘x’ marks), as it pushes them from a random initial point towards
each group’s center. Last, since training is an iterative process, node
embeddings and cluster centers attract each other in turns, explaining the
formulation of these distinct clusters.

##  4 Related Work

GRL has gained a lot of attention due to the need for automated processes that
can analyze large volumes of structured data, with graphs being the hallmark
of such structures.

Conventional graph embeddings: The first efforts exploited well-known graph
mechanisms to calculate node representations. DeepWalk (Perozzi, Al-Rfou, and
Skiena 2014) and Node2Vec (Grover and Leskovec 2016) utilize random walks to
sample the graph and train a Word2Vec model on these samples to extract the
embeddings. Also, TADW (Yang et al. 2015) applies non-negative matrix
factorization on both the graph and node features to get a consistent
partition. Last, DNGR (Cao, Lu, and Xu 2016) employs denoising auto encoders
to find low dimensional representations and then reconstruct the graph
adjacency.

GNN-based methods: Graph Neural Networks are designed to capture graph
structures, and thus have been used for learning node representations. VGAE
(Kipf and Welling 2016b) uses GCNs to form a variational autoencoder which
learns to generate node embeddings, while ARVGA (Pan et al. 2018) uses
adversarial learning to train the graph auto encoder. DGI (Veličković et al.
2018) leverages both local and global graph information for representation
learning using contrastive learning, while GIC (Mavromatis and Karypis 2020)
extends DGI by forming node clusters to better separate nodes in the embedding
space. In particular ClusterNet (Wilder et al. 2019) –the clustering process
of GIC which is crucial for its superior performance– is also incorporated in
PointSpectrum aiding in performance and validating GIC’s design. Although
efficient, to capture deep graph interactions GNN methods are inevitably led
to over smoothing, where node representations converge to indistinguishable
vectors (Chen et al. 2020; Zhou et al. 2020).

Spectral methods: On the other hand, spectral methods exploit graph filters to
perform high-order graph convolution at once, thus bypassing GNNs’ over
smoothing. AGC (Zhang et al. 2019) uses Laplacian filtering with spectral
clustering to cluster nodes into groups, while AGE (Cui et al. 2020) employs
an auto encoder to produce node embeddings through Laplacian smoothing. Also,
DAEGC (Wang et al. 2019) leverages an attentional network alongside soft-
labeling for self supervision to construct the embeddings. While spectral
methods address over smoothing, they have only used conventional neural
networks (MLPs, CNNs) that cannot capture graph properties (e.g.,
equivariance) by design; they can only learn the structural information
contained in the smoothed input signal.

PointSpectrum –although a spectral method– lies on the intersection of GNN-
based and spectral methods, alleviating over smoothing through graph filtering
and capturing structural information through set equivariant networks.

##  5 Conclusion

PointSpectrum is the first work to introduce the set equivariance property
(typically, a property of GNN-based methods) into spectral methods. Set
equivariance is important when learning on graph data, since it is inherently
designed to exploit the nature of unordered data. Our work was motivated by
this, and our experimental results clearly demonstrated the performance
benefits of using a set equivariant network (PointNetST) over the MLP or CNN
layers that are used in spectral methods.

We deem PointSpectrum as an initial effort (or as a proof of concept) in the
direction of integrating set equivariance with Laplacian smoothing. This is
why we adopted a simple design for the model architecture, without
exhaustively over-engineering its modules or tuning its hyperparameters.
Nevertheless, and despite this simplicity, we have shown that PointSpectrum
can achieve state-of-the-art results in benchmark datasets. This brings a
positive message for the efficiency, applicability and generalizability of our
approach to other spectral or more generic GRL methods.

In particular, we identify the following as promising directions for future
research:

Extensions: Set equivariant networks (e.g., DeepSet or PointNetST) can easily
be introduced to existing spectral methods (e.g., AGC, AGE or DAEGC) by
replacing the MLP or CNN layers that they use. A more challenging direction is
the extension of the proposed approach to generative models, such as VAE or
GAN architectures.

Generalization: As shown, PointSpectrum performs well even under data
permutations. A deeper understanding (experimental/theoretical) of its
capacity to generalize on noisy, corrupted or unseen data, could provide
further insights on the mechanics of using set equivariant methods on graphs,
as well as lead to the design of more efficient GRL methods.

Unification: PointSpectrum has a modular design, where a set equivariant
network receives as input the smoothed matrix $\mathbf{\bar{X}}$. Unifying
these two operations in a single component (e.g., a new GNN layer), if
possible, could simultaneously aim at a higher performance and bypass over
smoothing.

## References

  * Cao, Lu, and Xu (2016) Cao, S.; Lu, W.; and Xu, Q. 2016.  Deep neural networks for learning graph representations.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 30.
  * Chen et al. (2020) Chen, D.; Lin, Y.; Li, W.; Li, P.; Zhou, J.; and Sun, X. 2020.  Measuring and relieving the over-smoothing problem for graph neural networks from the topological view.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, 3438–3445.
  * Cui et al. (2020) Cui, G.; Zhou, J.; Yang, C.; and Liu, Z. 2020.  Adaptive Graph Encoder for Attributed Graph Embedding.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 976–985.
  * Giles, Bollacker, and Lawrence (1998) Giles, C. L.; Bollacker, K. D.; and Lawrence, S. 1998.  CiteSeer: An automatic citation indexing system.  In _Proceedings of the third ACM conference on Digital libraries_ , 89–98.
  * Grover and Leskovec (2016) Grover, A.; and Leskovec, J. 2016.  node2vec: Scalable feature learning for networks.  In _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_ , 855–864.
  * He et al. (2015) He, K.; Zhang, X.; Ren, S.; and Sun, J. 2015.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In _Proceedings of the IEEE international conference on computer vision_ , 1026–1034.
  * Horn and Johnson (2012) Horn, R. A.; and Johnson, C. R. 2012.  _Matrix analysis_.  Cambridge university press.
  * Keriven and Peyré (2019) Keriven, N.; and Peyré, G. 2019.  Universal invariant and equivariant graph neural networks.  _Advances in Neural Information Processing Systems_ , 32: 7092–7101.
  * Kipf and Welling (2016a) Kipf, T. N.; and Welling, M. 2016a.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_.
  * Kipf and Welling (2016b) Kipf, T. N.; and Welling, M. 2016b.  Variational graph auto-encoders.  _arXiv preprint arXiv:1611.07308_.
  * Liu et al. (2019) Liu, N.; Tan, Q.; Li, Y.; Yang, H.; Zhou, J.; and Hu, X. 2019.  Is a single vector enough? exploring node polysemy for network embedding.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 932–940.
  * Mavromatis and Karypis (2020) Mavromatis, C.; and Karypis, G. 2020.  Graph InfoClust: Leveraging cluster-level node information for unsupervised graph representation learning.  _arXiv preprint arXiv:2009.06946_.
  * McCallum et al. (2000) McCallum, A. K.; Nigam, K.; Rennie, J.; and Seymore, K. 2000.  Automating the construction of internet portals with machine learning.  _Information Retrieval_ , 3(2): 127–163.
  * Namata et al. (2012) Namata, G.; London, B.; Getoor, L.; Huang, B.; and EDU, U. 2012.  Query-driven active surveying for collective classification.  In _10th International Workshop on Mining and Learning with Graphs_ , volume 8, 1.
  * Pan et al. (2018) Pan, S.; Hu, R.; Long, G.; Jiang, J.; Yao, L.; and Zhang, C. 2018.  Adversarially regularized graph autoencoder for graph embedding.  In _IJCAI International Joint Conference on Artificial Intelligence_.
  * Perozzi, Al-Rfou, and Skiena (2014) Perozzi, B.; Al-Rfou, R.; and Skiena, S. 2014.  Deepwalk: Online learning of social representations.  In _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 701–710.
  * Sannai, Takai, and Cordonnier (2019) Sannai, A.; Takai, Y.; and Cordonnier, M. 2019.  Universal approximations of permutation invariant/equivariant functions by deep neural networks.  _arXiv preprint arXiv:1903.01939_.
  * Segol and Lipman (2019) Segol, N.; and Lipman, Y. 2019.  On Universal Equivariant Set Networks.  In _International Conference on Learning Representations_.
  * Sonoda and Murata (2017) Sonoda, S.; and Murata, N. 2017.  Neural network with unbounded activation functions is universal approximator.  _Applied and Computational Harmonic Analysis_ , 43(2): 233–268.
  * Taubin (1995) Taubin, G. 1995.  A signal processing approach to fair surface design.  In _Proceedings of the 22nd annual conference on Computer graphics and interactive techniques_ , 351–358.
  * Van der Maaten and Hinton (2008) Van der Maaten, L.; and Hinton, G. 2008.  Visualizing data using t-SNE.  _Journal of machine learning research_ , 9(11).
  * Veličković et al. (2018) Veličković, P.; Fedus, W.; Hamilton, W. L.; Liò, P.; Bengio, Y.; and Hjelm, R. D. 2018.  Deep Graph Infomax.  In _International Conference on Learning Representations_.
  * Wang et al. (2019) Wang, C.; Pan, S.; Hu, R.; Long, G.; Jiang, J.; and Zhang, C. 2019.  Attributed Graph Clustering: A Deep Attentional Embedding Approach.  In _International Joint Conference on Artificial Intelligence_. International Joint Conferences on Artificial Intelligence.
  * Wang et al. (2018) Wang, X.; Girshick, R.; Gupta, A.; and He, K. 2018.  Non-local neural networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 7794–7803.
  * Wilder et al. (2019) Wilder, B.; Ewing, E.; Dilkina, B.; and Tambe, M. 2019.  End to end learning and optimization on graphs.  _Advances in Neural Information Processing Systems_ , 32: 4672–4683.
  * Wu et al. (2019) Wu, F.; Souza, A.; Zhang, T.; Fifty, C.; Yu, T.; and Weinberger, K. 2019.  Simplifying graph convolutional networks.  In _International conference on machine learning_ , 6861–6871. PMLR.
  * Xu et al. (2018) Xu, K.; Li, C.; Tian, Y.; Sonobe, T.; Kawarabayashi, K.-i.; and Jegelka, S. 2018\.  Representation learning on graphs with jumping knowledge networks.  In _International Conference on Machine Learning_ , 5453–5462. PMLR.
  * Yang et al. (2015) Yang, C.; Liu, Z.; Zhao, D.; Sun, M.; and Chang, E. 2015.  Network representation learning with rich text information.  In _Twenty-fourth international joint conference on artificial intelligence_.
  * Yarotsky (2021) Yarotsky, D. 2021.  Universal approximations of invariant maps by neural networks.  _Constructive Approximation_ , 1–68.
  * Zaheer et al. (2017) Zaheer, M.; Kottur, S.; Ravanbhakhsh, S.; Póczos, B.; Salakhutdinov, R.; and Smola, A. J. 2017.  Deep Sets.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , 3394–3404.
  * Zhang and Chen (2019) Zhang, M.; and Chen, Y. 2019.  Inductive Matrix Completion Based on Graph Neural Networks.  In _International Conference on Learning Representations_.
  * Zhang et al. (2019) Zhang, X.; Liu, H.; Li, Q.; and Wu, X. M. 2019.  Attributed graph clustering via adaptive graph convolution.  In _28th International Joint Conference on Artificial Intelligence, IJCAI 2019_ , 4327–4333. International Joint Conferences on Artificial Intelligence.
  * Zhang and Zitnik (2020) Zhang, X.; and Zitnik, M. 2020.  GNNGuard: Defending Graph Neural Networks against Adversarial Attacks.  _Advances in Neural Information Processing Systems_ , 33.
  * Zhao and Akoglu (2019) Zhao, L.; and Akoglu, L. 2019.  PairNorm: Tackling Oversmoothing in GNNs.  In _International Conference on Learning Representations_.
  * Zhou et al. (2020) Zhou, K.; Huang, X.; Li, Y.; Zha, D.; Chen, R.; and Hu, X. 2020.  Towards Deeper Graph Neural Networks with Differentiable Group Normalization.  _Advances in Neural Information Processing Systems_ , 33.

##  Appendix A Appendix

###  A.1 Datasets

Dataset | Nodes | Edges | Features | Classes
---|---|---|---|---
Cora | 2708 | 5429 | 1433 | 7
Citeseer | 3327 | 4732 | 3703 | 6
Pubmed | 19717 | 44338 | 500 | 3
Table 4: Dataset specifics

Table 4 presents the statistics of the datasets used throughout the
experimental process. These data contain a different number of labels, which
are used as the oracle information to calculate the reported metrics
(Accuracy, NMI, ARI and F1). All of them present a sparse graph structure,
while Pubmed contains less rich information in terms of node features in
comparison to Cora and Citeseer.

###  A.2 Hyperparameter setup

Dataset k Dropout LR Epochs Dim $\alpha$ (value) $\beta$ (value) Cora 5 0.2
0.01 500 100 const (1) const (2) Citeseer 1 0.2 0.01 500 100 expdec (1) exp
(5) Pubmed 7 0.2 0.01 500 100 const (1) const (2)

Table 5: Hyper-parameter values for different datasets. $\alpha$ and $\beta$
types are: constant (const), exponential increase (exp) and exponential
decrease (expdec). k refers to convolution order, LR to learning rate and Dim
to encoder’s dimensions.

To conduct the experiments and validate PointSpectrum’s performance, hyper
parameter tuning is needed. The values corresponding to each dataset are
presented in Table 5. It should be noted that the best value for convolution
order is smaller for PointSpectrum when compared to other methods that employ
graph filtering (8, 6 and 8 for Cora, Citeseer and Pubmed respectively). This
showcases the fact that set equivariant networks can capture structural
information more easily and thus they do not need the whole information to be
presented explicitly.

Regarding hyper parameters $\alpha$ and $\beta$, various configurations were
investigated. Specifically, we point out the below behaviors:

  * •

constant: the hyper parameter has a constant value throughout training

  * •

linear: the hyper parameter linearly increases (decreases) in every epoch to
reach a maximum (minimum) value, which is also provided by the user

  * •

exponential: the hyper parameter exponentially increases (decreases) in every
epoch to reach a maximum (minimum) value, which is also provided by the user.
Specifically, given the maximum value $s$ and the number of epochs $e$ the
following function is used: $f(x)=\exp{(\frac{\log{1+s}}{e}x)}-1$ for a given
epoch x. For the decreasing values, we sort this function’s results in
decreasing order.

###  A.3 Ablation study

Method Conventional AE (MLP) Conventional AE (CNN) \+ PointNetST \+ ClusterNet
Cora ACC NMI ARI F1 0.578 0.414 0.333 0.526 0.610 0.423 0.362 0.560 0.645
0.482 0.428 0.561 0.736 0.529 0.516 0.711 Citeseer ACC NMI ARI F1 0.480 0.215
0.198 0.428 0.465 0.212 0.189 0.415 0.673 0.393 0.407 0.595 0.703 0.430 0.451
0.613 Pubmed ACC NMI ARI F1 0.607 0.248 0.206 0.596 0.594 0.231 0.189 0.584
0.531 0.207 0.127 0.539 0.776 0.375 0.444 0.768

Table 6: Ablation study.

To validate the efficacy of PointSpectrum’s components an ablation study is
conducted. First a conventional autoencoder is tested using either an MLP or a
CNN encoder. Then PointNetST substitutes the conventional autoencoder and last
ClusterNet is also employed alongside reconstruction objective. As it can be
seen in Table 6, in all three datasets the holistic PointSpectrum model
achieves the best results. Furthermore, regarding Cora and Citeseer both set
equivariance (through PointNetST) and the clustering objective (through
ClusterNet) increase the model’s performance. However, for Pubmed although
clustering is beneficial, set equivariance does not seem to help. This may
relate to the low number of features when compared to the graph size, meaning
that the information captured from the conventional neural networks is
sufficient to characterize the data, while node features (and thus their
permutations) are not that important.

To verify the above assumption we have also tested the three PointSpectrum
variants on a reduced number of features. Specifically, Figure 5 depicts this
experiment on Citeseer dataset where the number of features is large enough to
enable us different degrees of features reduction. Although performance
deterioration is not analogous to features reduction, a general trend is
shown: PointNetST is heavily dependent on features, while conventional neural
networks seem to pull closer to their full-features performance no matter the
reduction. However, this may come from conventional neural networks’ tendency
to overfit to the specific permutation, therefore a more thorough
investigation is needed which is out of this work’s scope.

(a) Accuracy (Cora)

(b) NMI (Cora)

(c) ARI (Citeseer)

(d) F1 (Citeseer)

Figure 5: PointNetST, MLP and CNN-based methods’ performance trained and
evaluated on reduced number of features (depicted as pointNet, mlp and cnn
respectively.

###  A.4 Additional visual results

Here the visual analyses of tSNE on Citeseer and Pubmed are presented. As
depicted, PointSpectrum behaves similar to Cora, separating the embeddings as
training proceeds and forcing cluster centers towards the centers of the node
groups that it creates. More concretely, in the case of Citeseer, nodes are
well separated into distinct clusters and therefore the trained ClusterNet
centers match to the actual centers. For Pubmed though, node separation is not
trivial and nodes appear to be similar to nodes of other clusters. We suppose
that the reason behind this phenomenon is the small number of available
features for PointSpectrum to exploit, when compared to Cora and Citeseer.

(a) Initial

(b) Intermediate

(c) Final

Figure 6: PointSpectrum’s training behavior on Citeseer (top) and Pubmed
(bottom) dataset using t-SNE for visualization. ClusterNet’s trainable centers
are denoted as black ‘x’ marks.

###  A.5 Influence of convolution order on Citeseer and Pubmed

(a) Accuracy (Citeseer)

(b) ARI (Citeseer)

(c) NMI (Citeseer)

(d) Accuracy (Pubmed)

(e) ARI (Pubmed)

(f) NMI (Pubmed)

Figure 7: Accuracy, ARI and NMI metrics for PointNetST, MLP and CNN-based
networks solving the clustering task on Citeseer and Pubmed datasets. For all
three measures, the mean value and standard deviation of 10 experiment runs
are depicted.

Influence of parameter k - the convolution order - is also presented with
respect to Citeseer and Pubmed in Figure 7. Citeseer presents similar behavior
to Cora as it has similar graph structure with many node attributes being
present. However, on Pubmed training behavior is slightly different. As shown,
PointNetST does not perform constantly better than its CNN variant. This can
be explained by the fact that node attributes are limited in Pubmed, while
graph structure is dominant. Thus, the conventional neural networks can
overfit on this structure and depict equally high performance compared to set
equivariant ones.

###  A.6 Training Convergence on Citeseer and Pubmed

Extending the discussion on training convergence, Figure 8 depicts the
comparison between PointNetST encoder and MLP and CNN ones. Again, Citeseer
behaves similar to Cora due to their similar structural and contextual
information. Moreover, as already discussed Pubmed presents a different graph
structure and less node information complicating set equivariance and
restricting its performance. However, despite these complications PointNetST
maintains its efficiency and accelerates the training convergence, although by
a much smaller factor, nearly indistinguishable from the rest methods.

(a) Loss (Citeseer)

(b) Reconstruction loss (Citeseer)

(c) Clustering loss (Citeseer)

(d) Loss (Pubmed)

(e) Reconstruction loss (Pubmed)

(f) Clustering loss (Pubmed)

Figure 8: Loss, reconstruction and clustering loss for PointNetST, MLP and
CNN-based networks solving the clustering task on Citeseer and Pubmed
datasets. For all three measures, the mean value and standard deviation of 10
experiment runs are depicted. PointNetST helps the model to converge faster
than the MLP and CNN variants.

###  A.7 Laplacian Smoothing and Graph Convolution

The most important notion in the prevalent GNN-based embedding methods, such
as GCN (Kipf and Welling 2016a), is that neighboring nodes should be similar
and hence their features should be smoother - than that of irrelevant nodes -
in the graph manifold. However, these methods capture deeper connections by
stacking multiple layers, leading to deep architectures, which are known to
overly smooth the node features (Chen et al. 2020). To address this problem,
the domain of graph signal processing considers $\mathbf{x}\in\mathbb{R}^{n}$
as a graph signal, where each one of the $n$ nodes is assigned a scalar. Then,
the smoothness of signal $\mathbf{x}$ depicts the similarity between all of
the graph nodes. To calculate smoothness, the Rayleigh quotient (Horn and
Johnson 2012) over the signal and the graph Laplacian $\mathbf{L}$ \-
essentially the normalized variance of $\mathbf{x}$ \- is employed:

$R(\mathbf{L},\mathbf{x})=\frac{\mathbf{x}^{T}\mathbf{L}\mathbf{x}}{\mathbf{x}^{T}\mathbf{x}}=\frac{\sum_{(i,j)\in\mathcal{E}(x_{i}-x_{j})^{2}}}{\sum_{i\in\mathcal{V}}x^{2}_{i}}$
(9)

Since neighboring nodes should be similar, a smoother signal is expected to
have lower Rayleigh quotient. To find the relation between eigenvalues and
Rayleigh quotient, one needs to calculate the eigendecomposition of the graph
Laplacian, that is $\mathbf{L}=\mathbf{U}\mathbf{\Lambda}\mathbf{U}^{-1}$ with
$\mathbf{U}\in\mathbb{R}^{n\times n}$ being the matrix of eigenvectors and
$\mathbf{\Lambda}=diag(\lambda_{1},\lambda_{2},\dots,\lambda_{n})$ the
diagonal matrix of eigenvalues. Then, the Rayleigh quotient of the eigenvector
$\mathbf{u_{i}}$ is:

$R(\mathbf{L},\mathbf{u_{i}})=\frac{\mathbf{u_{i}}^{T}\mathbf{L}\mathbf{u_{i}}}{\mathbf{u_{i}}^{T}\mathbf{u_{i}}}=\lambda_{i}$
(10)

It can be seen that the lower Rayleigh quotients - and by extension the
smoother eigenvectors - are correlated with low eigenvalues, meaning low
frequencies. To employ these observations to every signal $\mathbf{x}$, the
decomposition of x on the basis of $\mathbf{L}$ is considered:

$\mathbf{x}=\mathbf{U}\mathbf{p}=\sum_{i=1}^{n}p_{i}\mathbf{u_{i}}$ (11)

Consequently, as smooth signals are associated with smooth eigenvectors and
low eigenvalues according to Eq. 10, the used filter should cancel high
frequencies and preserve the low ones. Laplacian smoothing filters are
selected for this purpose, as they combine high performance with low
computational cost (Taubin 1995).

Laplacian Smoothing Filter: Here, we consider the generalized Laplacian
Smoothing filter as defined in (Taubin 1995)

$\mathbf{H}=\mathbf{I}-k\mathbf{L}$ (12)

where $k\in\mathbb{R}$, I is the identity matrix and $\mathbf{H}$ is the
filter matrix. Using Eq. 12, the filtered signal is:

$\displaystyle\mathbf{\bar{x}}$
$\displaystyle=\mathbf{H}\mathbf{x}=\mathbf{U}(\mathbf{I}-k\mathbf{\Lambda})\mathbf{U}^{-1}\mathbf{U}\mathbf{p}$
$\displaystyle=\sum_{i=1}^{n}(1-k\lambda_{i})p_{i}\mathbf{u_{i}}$

What this suggests is that for $\mathbf{H}$ to be low-pass, $1-k\lambda$
should always decline. It has been found that the optimal value of $k$ is
$1/\lambda_{max}$, with $\lambda_{max}$ denoting the largest eigenvalue (Cui
et al. 2020).

Having defined the filter, one can introduce k-order smoothing - and thus
graph convolution - by stacking k filters together. Ultimately, the overall
smoothed feature matrix is

$\mathbf{\bar{X}}=\mathbf{H^{k}}\mathbf{X}$ (13)

###  A.8 System Specifications

All of the experiments were conducted using a computing grid with an Intel
Xeon E5-2630 v4 CPU, 32Gb RAM and an Nvidia Tesla P100 GPU. Also, to speed up
some computations a personal computer with an Intel(R) Core(TM) i7-6700K CPU @
4.00GHz, 32Gb RAM and an NVidia GeForce GTX 1070 GPU was also employed for
specific experiments alongside the ones running on the grid.