summaries: This paper proposes a novel 3D point cloud representation learning framework. At the core of this method, is a lifting scheme inspired by wavelet decomposition. The proposed method roughly splits the input data in half at each stage, producing a down-sampled approximation C and detail d. Then C is further processed by the next layer, forming a multiscale pyramid. In summary, the contribution of this paper is:  1. Proposed to use the lifting scheme in point cloud processing, using graph convolution networks and transformers as backbone.  2. Evaluated the method against state-of-the-art baselines and showed that the proposed scheme performs well.  This paper proposes a new 3D shape representation learning method using multi-scale wavelet decomposition. In particular, the authors introduce a neural network architecture that decomposed 3D shapes into sub-bands components at multiple scales. In particular, starting from a pointcloud the proposed model learns to decompose it into coarse (high frequency) and detail (low frequency) components using an adaptive lifting scheme, similar to the original lifting scheme introduced for defining second-generation wavelets. Subsequently, two transformer models are used to refine the coarse and approximate geometry of the 3D shape. The proposed model achieves state-of-the-art results on the shape classification task on the ModelNet40 and the ScanObjectNN dataset and on the part segmentation task on the ShapeNet Part dataset. The concept of using such an adaptive lifting scheme seems to facilitate learning and to the best of my knowledge is novel for the case of shape representation learning. This paper presents a novel framework for 3D shape representation learning, which is based on multi-scale wavelet decomposition. This is very different from existing works. A novel transformer-based neural network, AWT-Net, is also proposed. The paper presents a new deep neural network architecture for 3D point cloud representation learning, based on wavelet decomposition. In particular, the authors propose a data-driven adaptive lifting scheme that introduces non-linearity into wavelet. The original linear operators update(U) and predict(P) in wavelet decomposition are replaced by non-linear graph convolutional networks (GCN). Equipped with wavelet transform and Transformers, the proposed network aims to captures and refines the holistic and complementary geometry of 3D shapes to supplement neighboring local information. Experimental results on standard benchmarks (i.e., shape classification and part segmentation) show that it achieves state-of- the-arts or competitive performance.
abstractText: We present a novel method for 3D shape representation learning using multi-scale wavelet decomposition. Distinct from previous works that either decompose 3D shapes into complimentary components at a single scale, or naively adopt up/down-sampling to build hierarchies and treat all points or local regions equally, we decompose 3D shapes into sub-bands components at multiple scales and all scales form a decomposition tree in a principled manner rooted in multi-resolution wavelet analysis. Specifically, we propose Adaptive Wavelet Transformer Network (AWT-Net) that firstly generates approximation or detail wavelet coefficients per point, classifying each point into high or low sub-bands components, using lifting scheme at multiple scales recursively and hierarchically. Then, AWT-Net exploits Transformers that regard the features from different but complementary components as two holistic representations, and fuse them with the original shape features with different attentions. The wavelet coefficients can be learned without direct supervision on coefficients, and AWT-Net is fully differentiable and can be learned in an end-to-end fashion. Extensive experiments demonstrate that AWT-Net achieves state-of-the-art or competitive performance on 3D shape classification and segmentation benchmarks.
references.authors: Nicolas Carion Francisco Massa Gabriel Synnaeve Nicolas Usunier Alexander Kirillov Sergey Zagoruyko
references.title: End-to-end object detection with transformers
references.venue: In Proceedings of the European Conference on Computer Vision,
references.authors: Jingdao Chen Yong Kwon Cho Zsolt Kira
references.title: Multi-view incremental segmentation of 3-d point clouds for mobile robots
references.venue: IEEE Robotics and Automation Letters,
references.authors: Mark Chen Alec Radford Rewon Child Jeffrey Wu Heewoo Jun David Luan Ilya Sutskever
references.title: Generative pretraining from pixels
references.venue: In International Conference on Machine Learning,
references.authors: Krzysztof Marcin Choromanski Valerii Likhosherstov David Dohan Xingyou Song Andreea Gane Tamas Sarlos Peter Hawkins Jared Quincy Davis Afroz Mohiuddin Lukasz Kaiser David Benjamin Belanger Lucy J Colwell Adrian Weller
references.title: Rethinking attention with performers
references.venue: In International Conference on Learning Representations,
references.authors: Roger L Claypoole Geoffrey M Davis Wim Sweldens Richard G Baraniuk
references.title: Nonlinear wavelet transforms for image coding via lifting
references.venue: IEEE Transactions on Image Processing,
references.authors: Zhigang Dai Bolun Cai Yugeng Lin Junying Chen
references.title: Up-detr: Unsupervised pre-training for object detection with transformers
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Zihang Dai Guokun Lai Yiming Yang Quoc Le
references.title: Funnel-transformer: Filtering out sequential redundancy for efficient language processing
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Ingrid Daubechies Wim Sweldens
references.title: Factoring wavelet transforms into lifting steps
references.venue: Journal of Fourier Analysis and Applications,
references.authors: Alexey Dosovitskiy Lucas Beyer Alexander Kolesnikov Dirk Weissenborn Xiaohua Zhai Thomas Unterthiner Mostafa Dehghani Matthias Minderer Georg Heigold Sylvain Gelly
references.title: An image is worth 16x16 words: Transformers for image recognition at scale
references.venue: In International Conference on Learning Representations,
references.authors: Haoqi Fan Bo Xiong Karttikeya Mangalam Yanghao Li Zhicheng Yan Jitendra Malik Christoph Feichtenhofer
references.title: Multiscale vision transformers
references.venue: arXiv preprint arXiv:2104.11227,
references.authors: Stephen Fitzpatrick Lambert Meertens
references.title: An experimental assessment of a stochastic, anytime, decentralized, soft colourer for sparse graphs
references.venue: In International Symposium on Stochastic Algorithms,
references.authors: Valentin Gabeur Chen Sun Karteek Alahari Cordelia Schmid
references.title: Multi-modal transformer for video retrieval
references.venue: In Proceedings of the European Conference on Computer Vision,
references.authors: Meng-Hao Guo Jun-Xiong Cai Zheng-Ning Liu Tai-Jiang Mu Ralph R Martin Shi-Min Hu
references.title: Pct: Point cloud transformer
references.venue: Computational Visual Media,
references.authors: Alfred Haar
references.title: Zur theorie der orthogonalen funktionensysteme
references.venue: Mathematische Annalen,
references.authors: Thomas Hitchcox James Richard Forbes
references.title: A point cloud registration pipeline using gaussian process regression for bathymetric slam
references.venue: IEEE International Conference on Intelligent Robots and Systems,
references.authors: Huaibo Huang Ran He Zhenan Sun Tieniu Tan
references.title: Wavelet-srnet: A wavelet-based cnn for multiscale face super resolution
references.venue: In Proceedings of the IEEE International Conference on Computer Vision,
references.authors: Drew A Hudson C Lawrence Zitnick
references.title: Generative adversarial transformers
references.venue: arXiv preprint arXiv:2103.01209,
references.authors: Le Hui Hang Yang Mingmei Cheng Jin Xie Jian Yang
references.title: Pyramid point cloud transformer for large-scale place recognition
references.venue: In Proceedings of the IEEE International Conference on Computer Vision,
references.authors: Li Jiang Hengshuang Zhao Shu Liu Xiaoyong Shen Chi-Wing Fu Jiaya Jia
references.title: Hierarchical point-edge interaction network for point cloud semantic segmentation
references.venue: In Proceedings of the IEEE International Conference on Computer Vision,
references.authors: Angelos Katharopoulos Apoorv Vyas Nikolaos Pappas François Fleuret
references.title: Transformers are rnns: Fast autoregressive transformers with linear attention
references.venue: In International Conference on Machine Learning,
references.authors: Thomas N Kipf Max Welling
references.title: Semi-supervised classification with graph convolutional networks
references.venue: In International Conference on Learning Representations,
references.authors: Nikita Kitaev Lukasz Kaiser Anselm Levskaya
references.title: Reformer: The efficient transformer
references.venue: In International Conference on Learning Representations,
references.authors: Shiyi Lan Ruichi Yu Gang Yu Larry S Davis
references.title: Modeling local geometric structure of 3d point clouds using geo-cnn
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Yangyan Li Rui Bu Mingchao Sun Wei Wu Xinhan Di Baoquan Chen
references.title: Pointcnn: Convolution on x-transformed points
references.venue: Advances in Neural Information Processing Systems,
references.authors: Yiqun Lin Zizheng Yan Haibin Huang Dong Du Ligang Liu Shuguang Cui Xiaoguang Han
references.title: Fpconv: Learning local flattening for point convolution
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Zhi-Hao Lin Sheng-Yu Huang Yu-Chiang Frank Wang
references.title: Convolution in the cloud: Learning deformable kernels in 3d graph convolution networks for point cloud analysis
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Lin Liu Jianzhuang Liu Shanxin Yuan Gregory Slabaugh Aleš Leonardis Wengang Zhou Qi Tian
references.title: Wavelet-based dual-branch network for image demoiréing
references.venue: In Proceedings of the European Conference on Computer Vision,
references.authors: Xinhai Liu Zhizhong Han Yu-Shen Liu Matthias Zwicker
references.title: Point2sequence: Learning the shape representation of 3d point clouds with an attention-based sequence to sequence network
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Yongcheng Liu Bin Fan Gaofeng Meng Jiwen Lu Shiming Xiang Chunhong Pan
references.title: Densepoint: Learning densely contextual representation for efficient point cloud processing
references.venue: In Proceedings of the IEEE International Conference on Computer Vision, pp. 5239–5248,
references.authors: Yongcheng Liu Bin Fan Shiming Xiang Chunhong Pan
references.title: Relation-shape convolutional neural network for point cloud analysis
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Ze Liu Yutong Lin Yue Cao Han Hu Yixuan Wei Zheng Zhang Stephen Lin Baining Guo
references.title: Swin transformer: Hierarchical vision transformer using shifted windows
references.venue: arXiv preprint arXiv:2103.14030,
references.authors: Jiageng Mao Xiaogang Wang Hongsheng Li
references.title: Interpolated convolutional networks for 3d point cloud understanding
references.venue: In Proceedings of the IEEE International Conference on Computer Vision,
references.authors: Sunil K Narang Antonio Ortega
references.title: Lifting based wavelet transforms on graphs
references.venue: In Proceedings of Asia-Pacific Signal and Information Processing Association,
references.authors: Edouard Oyallon Eugene Belilovsky Sergey Zagoruyko
references.title: Scaling the scattering transform: Deep hybrid networks
references.venue: In Proceedings of the IEEE International Conference on Computer Vision,
references.authors: Adam Paszke Sam Gross Francisco Massa Adam Lerer James Bradbury Gregory Chanan Trevor Killeen Zeming Lin Natalia Gimelshein Luca Antiga
references.title: Pytorch: An imperative style, high-performance deep learning library
references.venue: Advances in Neural Information Processing Systems,
references.authors: Charles R Qi Hao Su Kaichun Mo Leonidas J Guibas
references.title: Pointnet: Deep learning on point sets for 3d classification and segmentation
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Charles R Qi Wei Liu Chenxia Wu Hao Su Leonidas J Guibas
references.title: Frustum pointnets for 3d object detection from rgb-d data
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Charles Ruizhongtai Qi Li Yi Hao Su Leonidas J Guibas
references.title: Pointnet++: Deep hierarchical feature learning on point sets in a metric space
references.venue: Advances in Neural Information Processing Systems,
references.authors: Ali Rahimi Benjamin Recht
references.title: Random features for large-scale kernel machines
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Michael Ramamonjisoa Michael Firman Jamie Watson Vincent Lepetit Daniyar Turmukhambetov
references.title: Single image depth prediction with wavelet decomposition
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Maria Ximena Bastidas Rodriguez Adrien Gruson Luisa Polania Shin Fujieda Flavio Prieto Kohei Takayama Toshiya Hachisuka
references.title: Deep adaptive wavelet network
references.venue: In Proceedings of the IEEE Winter Conference on Applications of Computer Vision,
references.authors: Xuejian Rong Denis Demandolx Kevin Matzen Priyam Chatterjee Yingli Tian
references.title: Burst denoising via temporally shifted wavelet transforms
references.venue: In Proceedings of the European Conference on Computer Vision,
references.authors: Raif Rustamov Leonidas J Guibas
references.title: Wavelets on graphs via deep learning
references.venue: Advances in Neural Information Processing Systems,
references.authors: Fadil Santosa
references.title: Second generation wavelets: theory and application
references.venue: University of Minnesota, Institute for Mathematics and its Applications,
references.authors: Yiru Shen Chen Feng Yaoqing Yang Dong Tian
references.title: Mining point cloud local structures by kernel correlation and graph pooling
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Weijing Shi Raj Rajkumar
references.title: Point-gnn: Graph neural network for 3d object detection in a point cloud
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Wim Sweldens
references.title: Wavelets and the lifting scheme: A 5 minute tour
references.venue: Journal of Applied Mathematics and Mechanics,
references.authors: Wim Sweldens
references.title: The lifting scheme: A construction of second generation wavelets
references.venue: SIAM Journal on Mathematical Analysis,
references.authors: Yi Tay Dara Bahri Liu Yang Donald Metzler Da-Cheng Juan
references.title: Sparse sinkhorn attention
references.venue: In International Conference on Machine Learning,
references.authors: Hugues Thomas Charles R Qi Jean-Emmanuel Deschaud Beatriz Marcotegui François Goulette Leonidas J Guibas
references.title: Kpconv: Flexible and deformable convolution for point clouds
references.venue: In Proceedings of the IEEE International Conference on Computer Vision,
references.authors: Mikaela Angelina Uy Quang-Hieu Pham Binh-Son Hua Thanh Nguyen Sai-Kit Yeung
references.title: Revisiting point cloud classification: A new benchmark dataset and classification model on real-world data
references.venue: In Proceedings of the IEEE International Conference on Computer Vision,
references.authors: Ashish Vaswani Noam Shazeer Niki Parmar Jakob Uszkoreit Llion Jones Aidan N Gomez Łukasz Kaiser Illia Polosukhin
references.title: Attention is all you need
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Huiyu Wang Yukun Zhu Hartwig Adam Alan Yuille Liang-Chieh Chen
references.title: Max-deeplab: Endto-end panoptic segmentation with mask transformers
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Yue Wang Yongbin Sun Ziwei Liu Sanjay E Sarma Michael M Bronstein Justin M Solomon
references.title: Dynamic graph cnn for learning on point clouds
references.venue: Acm Transactions On Graphics,
references.authors: Travis Williams Robert Li
references.title: Wavelet pooling for convolutional neural networks
references.venue: In International Conference on Learning Representations,
references.authors: Wenxuan Wu Zhongang Qi Li Fuxin
references.title: Pointconv: Deep convolutional networks on 3d point clouds
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Zhirong Wu Shuran Song Aditya Khosla Fisher Yu Linguang Zhang Xiaoou Tang Jianxiong Xiao
references.title: 3d shapenets: A deep representation for volumetric shapes
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Saining Xie Sainan Liu Zeyu Chen Zhuowen Tu
references.title: Attentional shapecontextnet for point cloud recognition
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Mingye Xu Zhipeng Zhou Yu Qiao
references.title: Geometry sharing network for 3d point cloud classification and segmentation
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Mutian Xu Junhao Zhang Zhipeng Zhou Mingye Xu Xiaojuan Qi Yu Qiao
references.title: Learning geometry-disentangled representation for complementary understanding of 3d object point cloud
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Yifan Xu Tianqi Fan Mingye Xu Long Zeng Yu Qiao
references.title: Spidercnn: Deep learning on point sets with parameterized convolutional filters
references.venue: In Proceedings of the European Conference on Computer Vision,
references.authors: Li Yi Vladimir G Kim Duygu Ceylan I-Chao Shen Mengyan Yan Hao Su Cewu Lu Qixing Huang Alla Sheffer Leonidas Guibas
references.title: A scalable active framework for region annotation in 3d shape collections
references.venue: ACM Transactions on Graphics,
references.authors: Li Yi Hao Su Xingwen Guo Leonidas J Guibas
references.title: Syncspeccnn: Synchronized spectral cnn for 3d shape segmentation
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Xumin Yu Yongming Rao Ziyi Wang Zuyan Liu Jiwen Lu Jie Zhou
references.title: Pointr: Diverse point cloud completion with geometry-aware transformers
references.venue: In Proceedings of the IEEE International Conference on Computer Vision,
references.authors: Yanhong Zeng Jianlong Fu Hongyang Chao
references.title: Learning joint spatial-temporal transformations for video inpainting
references.venue: In Proceedings of the European Conference on Computer Vision,
references.authors: Dong Zhang Hanwang Zhang Jinhui Tang Meng Wang Xiansheng Hua Qianru Sun
references.title: Feature pyramid transformer
references.venue: In Proceedings of the European Conference on Computer Vision,
references.authors: Xizhou Zhu Weijie Su Lewei Lu Bin Li Xiaogang Wang Jifeng Dai
references.title: Deformable detr: Deformable transformers for end-to-end object detection
references.venue: In International Conference on Learning Representations,
references.authors: Net Xu
references.title: We measure four scales. Note that GDA-Net consists of two building blocks, which is fairly comparable to “scale 2” in our model. In this case, though our model contains around 25% more parameters, the execution time is only 13% (+P) and 15% (+V) slower than GDA-Net, which shows the practicability of our model
sections.text: 1 INTRODUCTION
  Figure 1: The detail component of table, car, chair, and cup from the test set of ModelNet40 Wu et al. (2015). Colors represent the absolute values of the detail coefficients per point. The larger values (redder colors) indicate, the higher probability that the points locate on high-frequency parts, e.g., edges or non-flat areas. Such geometric representations are learned implicitly in the classification task.
  Analysis of 3D point cloud is a crucial topic in computer vision and graphics, and has wide applications in robotics Chen et al. (2019), autonomous driving Qi et al. (2018), and visual SLAM Hitchcox & Forbes (2020), etc. To better understand the 3D shapes, effective point cloud analysis techniques and methods are in great demand. With the thriving of deep learning, numerous welldesigned neural networks are applied to extract expressive semantics of 3D point clouds with layered operations, in contrast to low-level handcrafted shape descriptors. The pioneering work PointNet Qi et al. (2017a) learns a spatial encoding of each point using multi-layer percep-
  trons and aggregates all point features to a global shape representation. The follow-on work PointNet++ Qi et al. (2017b) adopts a hierarchical encoder-decoder structure to process local regions, which down-samples point clouds in layers and gradually interpolates them back to the original resolution. The following works learn 3D shape representation from different perspectives: Xu et al. (2018); Thomas et al. (2019) extend regular grid convolution to irregular 3D point clouds, Li et al. (2018); Wu et al. (2019) design local operations on point patches, Wang et al. (2019); Shi & Rajkumar (2020) treat point clouds as graphs and apply graph convolution networks, to name a few.
  An interesting yet challenging problem is how to decompose 3D shapes into interpretable representations and exploit them for better shape analysis. For instance, some attempts Wang et al. (2019); Lan et al. (2019) capture local geometric relations among center points and their neighbors. However, these works treat all points or local regions equally, making it hard to extract features of the most relevant and crucial geometric parts, e.g., areas containing flat planes or areas containing edges. Another challenging problem is how to analyze 3D shapes at multiple scales/resolutions in an explainable way. Though some works Qi et al. (2017b); Jiang et al. (2019) extract point cloud features hierarchically, these works build the hierarchy in spatial/semantic spaces based on pairwise point distance, which is less interpretable w.r.t. shape geometry.
  The geometric components with different frequencies in 3D shapes contain distinct geometric characteristics (e.g., high frequency components correspond to edges / sharp parts, while low frequency components correspond to flat areas / smooth parts) and provide complementary geometric information to the shape representations. To effectively learn 3D shape representations, it is desirable to separate these components and process them differently, rather than feed the whole shapes into a single processor. It, therefore, motivates us to decompose 3D shapes into sub-bands components. In this work, we propose a principled method for 3D shape representation learning rooted in wavelet transform. Theoretical properties of wavelets in signal processing, such as time-frequency localization and multi-resolution analysis, have been well studied, making it appropriate to fuse into deep neural networks with interpretability. Inspired by that, we propose to perform multi-resolution analysis within neural networks through lifting scheme Sweldens (1998) to achieve a data-driven wavelet transform. The multi-resolution analysis generates decomposed visual representations at each scale, which contributes to the interpretability of the network. The generated approximation or detail coefficients per point at each scale, corresponding to high or low frequency components, capture essential geometric interest for down-streaming tasks.
  Specifically, we first adapt wavelet transform that analyzes 1D temporal or 2D image signals to 3D shapes at different semantic levels and decompose the original point cloud into the approximation/coarse and detail components, as explained in Section 4.1 and 4.2. Next, in Section 4.3, we utilize Transfomers Vaswani et al. (2017); Choromanski et al. (2021) to pay different attention to features from approximation and detailed variation components, and then fuse them with the original point features, respectively. As shown in Figure 1, the approximation and detail components have distinct but complementary effects on reflecting the geometry of 3D shapes. Equipped with wavelet transform and Transformers, we propose Adaptive Wavelet Transformer Network (AWTNet) that captures and refines the holistic and complementary geometry of 3D shapes to supplement neighboring local information. AWT-Net is trained using the loss functions proposed in Section 4.4. Experimental results on challenging benchmarks demonstrate that our AWT-Net achieves state-ofthe-art or competitive performance on 3D shape classification and segmentation tasks. Comprehensive analysis and visualizations verify that our model effectively extracts the complementary geometric features from two decomposed components at multiple scales. For example, as shown in Figure 1, we observe that our model can learn meaningfully samplings of point clouds in different categories and can detect key regions consistently within a semantic class, e.g., it separates chair legs and backs from chair seat, and separates cup handle from the body.
sections.heading: 2 RELATED WORK
sections.text: Geometric Point Cloud Models. PointNet Qi et al. (2017a) and DeepSet Zaheer et al. (2017) are pioneering neural network models that directly process point cloud to learn a spatial encoding of each point and then aggregate all individual point features to a holistic representation. Point-Net++ Qi et al. (2017b) partitions point cloud into overlapping local regions by the distance metric of spatial and/or semantic spaces and extracts local features capturing fine geometric structures from neighbors hierarchically. DGCNN Wang et al. (2019) reconstructs the k-NN graph using nearest neighbors in feature space to capture local geometric structure while maintaining permutation invariance. GeoCNN Lan et al. (2019) defines a convolution operation that aggregates edge features to capture the local geometric relations. Xu et al. (2020) aggregates points from local neighbors with similar semantics in both Euclidean and Eigenvalue space. RS-CNN Liu et al. (2019c) extends regular CNN to encode geometric relation in a local point set by learning the topology. DensePoint Liu et al. (2019b) recognizes the implicit geometry by extracting contextual shape semantics. Our model learns point
  cloud geometry from a novel perspective, i.e., multi-resolution wavelet analysis which is extensively applied in signal processing but seldom explored for 3D shapes.
  Wavelet in Vision. Theoretical properties of multi-resolution analysis using wavelets have been well studied, making such approaches more interpretable than CNNs. Several prior works incorporate wavelet representations into CNNs. Oyallon et al. (2017) proposed a hybrid network that replaces the first layers of ResNet with a wavelet scattering network. This modified ResNet resulted in comparable performance to the original ResNet but has a smaller number of trainable parameters. The wavelet pooling layer proposed in Williams & Li (2018) subsamples image features based on second-level wavelet decomposition. Wavelet-SRNet Huang et al. (2017) reconstructs super-resolution images from multi-scale wavelet coefficients estimated from low-resolution images under coefficient supervision. Similar scheme is adapted in Liu et al. (2020) for image demoiréing and Rong et al. (2020) for burst denoising. In Ramamonjisoa et al. (2021), they decompose a single image using Haar Transform and then reconstruct depth images hierarchically through inverse discrete wavelet transform. All of the mentioned works use pre-defined Haar wavelet which is less flexible for complex 3D shapes. Rustamov & Guibas (2013) adopts lifting scheme but still restricts to linear transformations of Haar coefficients for graph signals. DAWN-Net Rodriguez et al. (2020) uses lifting scheme to implicitly define wavelet transform functions for image recognition. Applying lifting scheme to learn 3D shape representations is more challenging as amounts of shape points are arranged irregularly, and as far as we know, we are among the first to tackle this problem.
  Transformer in Vision. The seminal work to adapt Transformer Vaswani et al. (2017) to vision tasks commences with Vision Transformer (ViT) Dosovitskiy et al. (2020) and Detection Transformer Carion et al. (2020). Since then, various applications of Transformer in vision are proposed, including: semantic segmentation Wang et al. (2021); Zhang et al. (2020), generative modeling Chen et al. (2020); Hudson & Zitnick (2021), object detection Zhu et al. (2021); Dai et al. (2021), video analysis Gabeur et al. (2020); Zeng et al. (2020), to name a few. PCT Guo et al. (2021) applies Transformer in 3D point cloud classification and segmentation. Concurrent works include two types of Point Transfomer proposed by Zhao et al. (2021) and Engel et al. (2021). GDA-Net is built on graph spectral theory and uses a 2-order polynomial approximation (Laplacian) as the filter and applies it to a graph to disentangle the graph into high and low frequency components. Thus, the decomposition process in is deterministic and static. PoinTr Yu et al. (2021) converts a point cloud to a sequence of point proxies and employs Transformer for point cloud completion. PPT-Net Hui et al. (2021) adopts Transformer for large-scale place recognition. MViT Fan et al. (2021) and Swin Liu et al. (2021) connect multi-scale feature hierarchies with transformer models by applying different Transformers for features with distinct spatial resolutions. Since multi-scale discrete wavelet transform decomposes point clouds at each subsequent scales, it is intrinsically essential to combine with Transformer in a similar way as in MViT and Swin. Due to quadratic computational complexity of self-attention, Fast Autoregressive Transformers Katharopoulos et al. (2020) is among the first to address the quadratic complexity by using the associativity property of matrix products. Some recent works Kitaev et al. (2020); Dai et al. (2020); Tay et al. (2020); Choromanski et al. (2021) propose efficient Transformers for long sequences. These models can be also adapted for vision tasks and the one proposed in Choromanski et al. (2021) is explored in our work.
sections.heading: 3 BACKGROUND
sections.text: We briefly review wavelet transform and lifting scheme as the building blocks of our model. We refer the reader to Sweldens (1996); Claypoole et al. (2003); Rodriguez et al. (2020) for more information.
  Wavelet Transform/Decomposition. Let us consider a continuous scalar function of a single variable f(x). Wavelet transform is to find a basis generated by a mother wavelet, denoted by ψ(x), to represent f(x) with a few parameters. The basic rule for generating this basis is to translate and dilate ψ(x), i.e., ψ(2jx− i), where j and i are integers. The basis is localized in both time (controlled by i) and scale/frequency (controlled by j) domains. The original function f(x) is decomposed as a linear combination of the basis:
  f(x) = ∑ j,i aj,iψ(2 jx− i) , (1)
  where aj,i are the wavelet coefficients of f(x) and can be computed as the inner product of ψ(2jx − i) with f(x). For a discretized signal x[n] (n ∈ Z), we sample points from ψ(2jx − i)
  to form filter banks to decompose x[n]. This is classical or first-generation wavelet Santosa (2011). Some commonly used mother wavelets include Haar wavelet Haar (1910), Daubechies wavelet, Biorthogonal wavelet Daubechies (1992), to name a few. Wavelet transform provides a nice framework for multi-resolution analysis of functions, i.e., the wavelet transform generates coarser and coarser versions of the same function while keeps track of the details missed going from fine to coarse. However, the first-generation wavelet mainly works well for infinite or periodic signals, which are rare in many applications. It is still unclear how to design a proper basis for any arbitrary signals sampled irregularly from a bounded domain. One solution is to give up designing a mother wavelet manually. Instead, the decomposition is entirely based on an approach called lifting scheme.
  Lifting Scheme. Lifting scheme, a.k.a., second-generation wavelets Sweldens (1998); Daubechies & Sweldens (1998), is a simple yet effective approach to define wavelets sharing the same properties as the first-generation wavelets. The lifting scheme takes as input a signal x and generates as outputs the approximation c and the detail d sub-bands of the wavelet transform. The lifting scheme consists of three stages Claypoole et al. (2003) as on the left panel of Figure 2.
  • Split. This stage splits the input signal into two non-overlapping partitions, e.g., the input signal x is divided into even xe and odd xo components, which are defined as xe[n] = x[2n] and xo[n] = x[2n+ 1].
  • Update (U). This stage separates the signal in frequency domain, generating the approximation c that has the same running average as the original input signal. Let xLUo [n] = xo[n − LU ], xo[n − LU + 1], · · · , xo[n + LU − 1], xo[n + LU ] denote the sequence of 2LU + 1 neighboring odd polyphase samples around xe[n]. The even polyphase samples are updated through an update operator U(·) on xLUo [n], resulting the approximation c as:
  c[n] = xe[n] + U(x LU o [n]) . (2)
  • Predict (P). As the partitions xe and xo are usually closely correlated, given one of them, it is feasible to build a predictor P (·) for the other, by tracking the difference (or detail) d among them. As the even component xe corresponds to the approximation c[n], it is possible to define P (·) as a function of c[n]. Let cLP [n] = c[n−LP ], c[n−LP +1], · · · , c[n+ LP − 1], c[n + LP ] denote a sequence of 2LP + 1 approximation coefficients. The odd polyphase samples are predicted as P (cLP [n]). The resulting prediction residual, or detail d, are computed as:
  d[n] = xo[n]− P (cLP [n]) . (3)
  Note that the update and predict operators U and P implicitly and effectively define the wavelet for decomposition.
sections.heading: 4 ADAPTIVE WAVELET TRANSFORMER NETWORK
sections.text: Overview. The update and predict operators in Eq. 2 and Eq. 3 are linear, which are incapable of learning geometry of 3D shapes. In this section, we propose a data-driven adaptive lifting scheme that introduces non-linearity into wavelet. Based on this scheme, we develop an Adaptive Wavelet Transformer Network, dubbed as AWT-Net, for 3D shape representation learning. The AWT-Net
  generates shape representations hierarchically, and the decomposition tree is shown on the left panel of Figure 3. Here we show three scales where each scale corresponds to a separate lifting process as illustrated on the left panel of Figure 2. We omit the split, update and predict blocks for conciseness. At each scale, the approximation ci serves the coarse version of the input signal while the detail di maintains the detailed difference between ci and the input signal. The approximation ci is further decomposed by another lifting process at the next scale. The AWT-Net is built based on this decomposition tree but replaces the linear operators U and P with non-linear neural networks. Once trained and fixed, the update U and predict P operators can be regarded as two sub-band basis/filters to subdivide the point cloud into high-frequency and low-frequency components, in analogy to the basis in Eq. 1. Its unrolled version is shown on the right panel of Figure 3.
  Each module in AWT-Net is described as follows.
sections.heading: 4.1 EVEN-ODD SPLIT
sections.text: Graph Construction. Assume a point cloud containing N points associated with features xi ∈ Rd, i ∈ {1, 2, · · · , N}. Features can be 3D coordinates, normals and/or high-dimensional features. We construct a k-NN graph G = (V, Ãu, Ãw), where each point xi corresponds to a node vi ∈ V , Ãu and Ãw ∈ RN×N are unweighted and weighted adjacency matrices encoding point similarity in feature space. The unweighted and weighted edges connecting two nodes vi and vj are defined as:
  Ãuij [, Ãwij ] = { 1 [, κ(∥xi − xj∥2)], xj ∈ N (xi) 0, otherwise , (4)
  where κ(·) is an non-negative function, e.g., Gaussian function, to ensure that Ãw is a diagonally dominant matrix andN represents neighborhood. Following Xu et al. (2021), we normalize all edge weights in each row in Aw to remove the impacts of varying neighborhood sizes and feature scales. Graph Split. We partition all nodes in a graph into two sets, containing even and odd nodes, respectively. Since lifting scheme uses information from odd (resp. even) nodes to update (resp. predict) even (resp. odd) nodes as in Eq. 2 (resp. Eq. 3), having all neighboring nodes with same parity means that local information cannot be used. Following Narang & Ortega (2009), we define the number of conflicts as the percentage of neighboring nodes that have the same parity after partition. The optimal splitting minimizes the number of conflicts. Theoretically, it is an NP-hard bipartite subgraph problem, but a heuristic solution can be found. We adapt the conservative fixed probability colorer (CFP) algorithm in Fitzpatrick & Meertens (2001), which is based on iteratively greedy local heuristics: at each iteration, a few randomly chosen nodes are activated, and each activated node counts the number of conflicting edges (i.e., connecting neighboring nodes with the same parity) and changes its parity based on the conflict. The algorithm is summarized in Algorithm 1.
  Algorithm 1: Even-Odd Node Split Require: A graph G = (V,Au) with unweighted adjacency, maximum number of iterations M
  1 Randomly assign initial parity (e.g., 1 for odd, 0 for even) to each node 2 for m = 1:M do 3 Activate each node with a probability sampled from a uniform distribution independently 4 for each activated node do 5 Choose a parity that minimizes its conflict with neighboring nodes
  /* Keep the number of odd and even nodes roughly the same */ 6 No, Ne ← number of nodes with parity1, parity0 7 if No > Ne then 8 Randomly flip ⌊No−Ne2 ⌋ odd nodes’ parity 9 else
  10 Randomly flip ⌊Ne−No2 ⌋ even nodes’ parity
sections.heading: 4.2 ADAPTIVE LIFTING SCHEME
sections.text: Based on nodes’ parity after the even-odd split, we rearrange nodes V to gather odd and even nodes, and also rearrange the weighted adjacency matrix Aw accordingly:
  V = ( Vodd Veven ) , Aw = ( FNo×No JNo×Ne KNe×No LNe×Ne ) ,
  where Vodd and Veven represent the sets of odd and even nodes. The sub-matrix F is the adjacency matrix of a subgraph containing odd nodes only. The submatrix J contains edges that do not have conflicts, i.e., edges connecting nodes with the opposite parity. Similar definitions for K and L. Unlike the linear lifting scheme introduced in Section 3, we propose data-dependent non-linear update and predict operators, implemented as neural networks whose parameters are adaptively optimized to capture complex shape geometry. Specifically, we apply two Graph Convolutional Networks (GCNs) proposed in Kipf & Welling (2017) as the update and predict operators, separately. The graph convolution allows us to compute the response of a node based on its neighbors decided by the adjacency matrix. Performing graph convolution is equal to performing message gather within a neighborhood around each center node, sharing similarities with the definitions of xLuo [n] and cLp [n] in Eq. 2 and Eq. 3. The non-linear update and predict stages at i-th scale are defined as:
  ci = Veven + GCN(Vodd,F) , (5) di = Vodd − GCN(ci,L) , (6)
  where ci and di represent the approximation and detail components at i-th scale. We repeat this process at each scale recursively and form a hierarchical decomposition tree, capturing shape geometry at multi-scales. The maximum number of scales can be decided analytically as log2N and the coarsest scale contains only a single point.
sections.heading: 4.3 TRANSFORMER FOR CROSS ATTENTION
sections.text: The approximation and detail components play different but complementary roles in representing 3D shape geometry, and thus should not be treated equally. To utilize different variation components gained from lifting scheme, we adopt Transformers Vaswani et al. (2017); Choromanski et al. (2021) to integrate different components with the original input shape features. The architecture of Transformers is shown on the right panel of Figure 2, and multi-head attention is defined as:
  Attention(Q,K, V ) = softmax(QK⊤)V , (7)
  where Q,K, V denote query, key and value, respectively.
  For approximation ci as coarse component at i-th scale, we set query, key and value to:
  Q = zi−1,K = ci, V = ci , (8)
  where the definition of zi is shown in Figure 3. Note that for the first scale (i.e., i = 1), we set Q = x as input. For detail di, as most of the values are close to zeros (explained in Subsection 4.4), directly feed them into Transformer yields sub-optimal results. Utilizing a nice property of wavelets, namely time-frequency localization1, we regard di as a multiplier to strengthen or weaken the context features. Formally, the query, key and value for detail di at i-th scale are set as:
  Q = zi−1,K = ci−1 ⊗ exp(di), V = ci−1 ⊗ exp(di) , (9)
  where ⊗ represents element-wise multiplication. For the first scale, we set both zi−1 and ci−1 to x. In the part segmentation task, since each point cloud contains 2048 points, to efficiently compute multi-head attention, we also test Performers Choromanski et al. (2021) in addition to the vanilla Transformers Vaswani et al. (2017). Briefly, Performers represent the (attention) softmax kernel in terms of the Gaussian kernel, and approximate the latter by sampling from the Fourier Transform Rahimi et al. (2007).
sections.heading: 4.4 LOSS FUNCTION
sections.text: End-to-end training is performed using the cross-entropy loss function, in combination with regularization terms, to enforce a wavelet decomposition structure during training. The loss function takes the form of Eq. 10, where K in the first term denotes the number of classes, yi and pi are the ground-truth and the predicted probability for belonging to class i, respectively.
  Loss =− K∑ i=1 yi log(pi) + λ1 S∑ i=1 SmoothL1(A2ci−1 − ci) + λ2 S∑ i=1 SmoothL1(di) . (10)
  In lifting scheme, a perfect output of Eq. 2, i.e., the series c[n], would be a coarse approximation of x[n] at half the resolution. In the second term, we enforce each lifted even node has the same local average as its corresponding node in the original graph. Due to the half resolution of ci compared with the input ci−1, we raise the adjacent matrix A to the power of two to capture the node features up to second-order neighbors, and minimize the difference between the input graph features and the coarser version across all the decomposition scales. The rationale for the third term is: if the underlying signal x[n] is locally smooth, the prediction residuals d[n] should be small. Thus, the third term promotes the minimization of the magnitude of detail coefficients d[n] in Eq. 3, indicating smaller energy is contained in d[n].
sections.heading: 5 EXPERIMENTS AND RESULTS
sections.text: We evaluate our model on 3D shape classification and part segmentation tasks on different datasets.
sections.heading: 5.1 IMPLEMENTATION DETAILS
sections.text: The number of the constructed neighborhoods at each stage is 64. The maximum number of iterations M used in the split Algorithm 1 is set to 10. The update U(·) and P (·) operators are implemented as two GCNs Kipf & Welling (2017) and the internal structure of each GCN is: ConvBN-ReLU-Dropout-Conv-BN. We use a two-heads attention in Transformer (for both the vanilla one and Performer). We implement our model in PyTorch Paszke et al. (2019). We use the SGD optimizer with momentum and weight decay set to 0.9 and 0.0001, respectively. For both 3D shape classification and 3D object part segmentation tasks, we train for 350 epochs. The initial learning rate is set to 0.1 and is dropped by 5x every 40 epochs and clipped at 0.9e− 5. The values of λ1 and λ2 are set to 0.1 for all tasks.
sections.heading: 5.2 OBJECT CLASSIFICATION
sections.text: We evaluate AWT-Net on ModelNet40 Wu et al. (2015) which contains 9843 training shapes and 2468 test shapes across 40 categories. Points are uniformly sampled from the mesh models by Qi
  1In analogy wave signals expanding time domain, for 3D shapes which expand in the spatial domain, this property can be rephrased as spatial-frequency localization.
  et al. (2017a). Following Wang et al. (2019); Xu et al. (2021), we translate shapes and then randomly shuffle points in the training set. Similar to Qi et al. (2017a;b), we perform several voting tests with random scaling and average the predictions during testing. The quantitative comparisons of the overall classification accuracy with the state-of-the-art methods are listed in Table 1. ‘+V’ denotes the vanilla Transformer Vaswani et al. (2017) and ‘+P’ denotes Performer Choromanski et al. (2021), a variant of the vanilla Transformer. AWT-Net with two scales achieves better or comparable performance with other methods using the same number of points as the input, as shown in Table 1.
  We also evaluate AWT-Net on ScanObjectNN by Uy et al. (2019) to examine the robustness to deformed and noisy objects scanned in the real world. We test on the OBJ ONLY and noisy OBJ BG splits, and the results are summarized in Table 2, where our model gets the comparable accuracy and performance drop from OBJ ONLY to OBJ BG.
  Method (time order) Points Accuracy
  PointNet Qi et al. (2017a) 1K 89.2 PointNet++ Qi et al. (2017b) 1K 90.7 SCN Xie et al. (2018) 1K 90.0 KCNet Shen et al. (2018) 1K 91.0 PointCNN Li et al. (2018) 1K 92.2 Point2Sequence Liu et al. (2019a) 1K 92.6 DGCNN Wang et al. (2019) 1K 92.9 InterpCNN Mao et al. (2019) 1K 93.0 RS-CNN Liu et al. (2019c) 1K 93.6 3D-GCN Lin et al. (2020b) 1K 92.1 FPConv Lin et al. (2020a) 1K 92.5 GSNet Xu et al. (2020) 1K 92.9 PointTransformer Zhao et al. (2021) 1K 93.7 PCT Guo et al. (2021) 1K 93.2 GDANet Xu et al. (2021) 1K 93.8
  AWT-Net +V (ours) 1K 93.5 AWT-Net +P (ours) 1K 93.9
  Table 1: Classification accuracy (%) on ModelNet40 dataset.
  Method OBJ ONLY OBJ BG Acc. drop
  PointNet Qi et al. (2017a) 79.2 73.3 ↓ 5.9 PointNet++ Qi et al. (2017b) 84.3 82.3 ↓ 2.0 SpiderCNN Xu et al. (2018) 79.5 77.1 ↓ 5.4 PointCNN Li et al. (2018) 87.9 85.8 ↓ 2.1 DGCNN Wang et al. (2019) 86.2 82.8 ↓ 3.4 GDANet Xu et al. (2021) 88.5 87.0 ↓ 1.5 AWT-Net +V (ours) 88.2 86.4 ↓ 1.8 AWT-Net +P (ours) 88.5 86.8 ↓ 1.7
  Table 2: Classification accuracy (%) w.r.t. noise on ScanObjectNN dataset.
sections.heading: 5.3 PART SEGMENTATION
sections.text: We evaluate AWT-Net with three scales for shape part segmentation on ShapeNet Part Yi et al. (2016) dataset, which contains 16881 shapes in 16 categories and is labeled in 50 parts where each shape has 25̃ parts. The same voting test in classification is adopted. The instance average, the class average, and each class mean Inter-over-Union (mIoU) are summarized in Table 3. AWTNet +P achieves the best performance with class mIoU of 85.0% and instance mIoU of 86.6%. It is worth noticing that AWT-Net performs better on objects with obvious boundaries such as bag, knife, laptop, and skateboard. Some qualitative segmentation results are visualized in Figure 4.
sections.heading: 6 ABLATION STUDY
sections.text: Experiments are conducted using Performer (‘+P’) and no voting during testing (unless specified).
  Module Analysis. We ablate each module in AWT-Net, and the results are listed in Table 4. When the Transformer takes as input the original point cloud and both approximation and detail components, the network achieves the best accuracy with 93.4%. AWT-Net also surpasses the architecture of only using k-NN with 1.1% improvement. Our method ultimately obtains an accuracy of 93.9% with voting tests. This experiment shows that the decomposed approximation and detail components capture different but complementary geometric features to get complete shape representation.
  Split Scheme. We replace the split of approximation and detail components with random and farthest point sampling (FPS). The results are listed in Table 5, where decomposing point clouds into approximation and detail components gets the highest accuracy. Empirically, our wavelet decomposition strategy localizes points carried with informative geometry instead of noisy points, which improves the robustness against noise.
  Adjacency Matrix Computation. The result of dynamic adjacency matrix calculation in Subsection 4.1 is shown in Table 6. We pre-compute the adjacency matrix on 3D coordinates to split point clouds, which gets the accuracy of 91.8%. Nevertheless, by dynamically calculating the adjacency matrix in high dimensional semantic space at different scales, our network gains 1.6% improvement. Figure 1 shows that our decomposition strategy successfully decomposes points into flat areas and areas containing edges. Note that we do not provide any supervision w.r.t. shape geometry.
  Decomposition Levels. We investigate the impact of the number of decomposition levels (i.e., resolution scales), and the results are summarized in Table 7. AWT-Net performs best on the overall accuracy when the decomposition level is set to 2. We also observe that for shapes with simple geometric structures (e.g., radio and wardrobe), more scales have a negative effect on the performance, as more scales make the network prone to over-fitting on these simple shapes. While for shapes with complex structures (e.g., stool and person), more scales are needed to capture both coarse and fine-grained geometric features. That is, the accuracy increases with more scales applied to geometrically more complex objects. We find out that the ModelNet40 dataset contains more geometrically simple objects than complex ones, which leads to the overall accuracy drops with more scales used.
  Robustness Analysis. First, the robustness of our network on sampling density is tested by using sparser points as the input to ATW-Net trained with 1024 points. Figure 5 lists the results. Although sparser points bring difficulties, ATW-Net still performs consistently across all density settings. Moreover, Table 8 summarizes the results of rotation robustness, where AWT-Net outperforms other compared methods, especially with 2.4% improvement than the second-best at (s/s). Last, our model is evaluated on ScanObjectNN Uy et al. (2019) that consists of noisy and deformed scanned objects with non-uniform surface density. Table 2 summarizes AWT-Net gains the comparable accuracy drop from OBJ ONLY to OBJ BG, proving that ATW-Net is robust against noise.
sections.heading: 7 CONCLUSION
sections.text: We propose AWT-Net for 3D shape representation learning. Rooted in wavelet transform, AWT-Net dynamically decomposes point clouds into approximation and detail components at multiple resolution scales, which respectively denotes the low and high sub-bands of point clouds recursively. Another core component is Transformer, which explores the relations between the original complete points and coarse and detail components to provide complementary geometric information for learning shape representations. Extensive experiments show that our method achieves state-of-the-art or comparable performances and is robust to noise.
sections.heading: A APPENDIX
sections.text: A.1 FIGURES AND TABLES FOR ABLATION STUDY
  Method ModelNet40 OBJ ONLY OBJ BG
  random 89.6 82.9 83.8 FPS 92.0 85.3 84.2 app.-det. 93.4 88.0 86.3
  Table 6: Impact of dynamic strategy.
  Number of scales 1 2 3 4
  Overall 92.5 93.4 93.1 91.3 Radio 90.0 83.5 75.0 75.0 Wardrobe 75.0 71.0 68.0 65.0 Stool 75.0 78.0 85.0 85.2
  Person 85.0 88.5 95.0 100.0
  Table 7: Effect of decomposition levels on ModelNet40. Note that the results are achieved without voting during inference.
  Method z/z s/s
  PointNet Qi et al. (2017a) 81.6 66.3 PointNet++ Qi et al. (2017b) 90.1 87.8 SpiderCNN Xu et al. (2018) 83.5 69.6 DGCNN Wang et al. (2019) 90.4 82.6
  GDANet Xu et al. (2021) 91.2 90.5
  AWT-Net (ours) 91.4 90.2
  Table 8: Accuracy comparisons of rotation on ModelNet40. z/z: both training and test samples are augmented by random rotation along the z axis; s/s: both training and test samples are augmented by random rotation along (x,y,z) three axis.
  A.2 EXECUTION TIME AND MODEL PARAMETERS
  In this subsection, we compare the number of parameters and computational overhead w.r.t. GDANet Xu et al. (2021) on ModelNet40 and the results are listed in Table 9. We measure four scales. Note that GDA-Net consists of two building blocks, which is fairly comparable to “scale 2” in our model. In this case, though our model contains around 25% more parameters, the execution time is only 13% (+P) and 15% (+V) slower than GDA-Net, which shows the practicability of our model. We also notice that Performer is faster than the vanilla Transformer, which is consistent with our motivation.
  A.3 RANDOMNESS IN EVEN-ODD NODE SPLIT
  In this subsection, we compare the effect of using even-odd split and random split in Algorithm 1 and the results are listed in Table 11. Using random split performers slightly worse than even-odd split. With even-odd split, we can separate any two connected nodes into two different sets to the best extent, thus ensuring each local area contains both even and odd nodes. However, with random split, some local areas might contain only one type of nodes, thus failing to be decomposed properly.
  A.4 CONFIGURATIONS OF MODULE ANALYSIS
  In Table 11, we provide a description of the configurations of module analysis listed in Table 4.