Graph Convolution with Low-rank Learnable Local Filters
Authors: Xiuyuan Cheng
Zichen Miao
Qiang Qiu
Venue: ICLR 2021 Spotlight (2021)

Abstract: Geometric variations like rotation, scaling, and viewpoint changes pose a significant challenge to visual understanding. One common solution is to directly model certain intrinsic structures, e.g., using landmarks. However, it then becomes non-trivial to build effective deep models, especially when the underlying non-Euclidean grid is irregular and coarse. Recent deep models using graph convolutions provide an appropriate framework to handle such non-Euclidean data, but many of them, particularly those based on global graph Laplacians, lack expressiveness to capture local features required for representation of signals lying on the non-Euclidean grid. The current paper introduces a new type of graph convolution with learnable low-rank local filters, which is provably more expressive than previous spectral graph convolution methods. The model also provides a unified framework for both spectral and spatial graph convolutions. To improve model robustness, regularization by local graph Laplacians is introduced. The representation stability against input graph data perturbation is theoretically proved, making use of the graph filter locality and the local graph regularization. Experiments on spherical mesh data, real-world facial expression recognition/skeleton-based action recognition data, and data with simulated graph noise show the empirical advantage of the proposed model.

Published as a conference paper at ICLR 2021
GRAPH CONVOLUTION WITH LOW-RANK LEARN- ABLE LOCAL FILTERS
Xiuyuan Cheng
Zichen Miao & Qiang Qiu
Department of Mathematics
Electrical and Computer Engineering
Duke University
Purdue University West Lafayette, IN, USA atiloz,qqquu @purdue.
Durham, NC, USA
xiuyuan. cheng@duke, edu
A ABSTRACT
Geometric variations like rotation, scaling, and viewpoint changes posc a significant challenge to visual understanding. One common solution is to directly model certain intrinsic structures, c.g., using landmarks. How- ever, it then becomes non-trivial to build effective deep models, especially when the underlying non-Euclidean grid is irregular and coarse. Recent deep models using graph convolutions provide an appropriate framework to handle such non non-Euclidean data, but many of them, particularly those based on global graph Laplacians, lack expressiveness to capture local fea- tures required for representation of signals lying on the non-Euclidean grid. The current paper introduces new type of graph convolution with learn- able low-rank local filters, which is provably more expressive than previous spectral graph convolution methods. The model also provides a unified framework for both spectral and spatial graph convolutions, To improve model robustness, regularization by local graph Laplacians is introduced. The representation stability against input graph data perturbation is theo- retically proved, making use of the graph filter locality and the local graph regularization. Experiments on spherical mesh data, real-world facial ex- pression recognition, /saeleton-based action recognition data, and data with simulated graph noise show the empirical advantage of the proposed model.
INTRODUCTION
Deep methods have achieved great success in visual cognition, yet they still lack capability to tackle severe geometric transformat such as rotation, scaling and viewpoint changes. This problem is often handled by conducting data augmentations with these geometric vari- ations included, e.g. by randomly rotating images, so as to make the trained model robust to these variations. However, this would remarkably increase the cost of training time and model parameters. Another way is to make use of certain underlying structures of objects, e.g. facial landmarks (Chen et al. 2013) and human skeleton landmarks (Vemulapalli et al. 2014a), c.f. Fig, [ (right). Nevertheless, these methods then adopt hand-crafted features based on landmarks, which greatly constrains their ability to obtain rich features for down- stream tasks. One of the main obstacles for feature extraction is the non-Euclidess property of underlying structures, and particularly, it prohibits the direct usage of prevalent convo- lutional noural network (CNN) architectures (He et al. 2016 Huang et al.) 2017). Whereas there are recent CNN models designed for non- Bon-ldal grids, c.g., for spherical mesh (Jiang et al. 2019 Cohen et al. 2018 Coors et al. 2018) and manifold mesh in computer graphics (Bronstein et al. 2017
Fey et al., 2018), they mainly rely on partial differential operators which only can be calculated preciscly on fine and regular mesh, and may not be applicable to the landmarks which are irregular and course. Recent works have also applied Graph Neural Network (GNN) approaches to coarse non- non-Euclidean data, yet methods using GCN (Kipf & Welling, 2016 may fall short model capacity, and other methods adopt- ing GAT (Velicković et al. 2017 are mostly heuristic and lacking theoretical analysis. A
detailed review is provided in Sec. 1.1
In this paper, we propose a graph convolution model, called L3Net, originating from low- rank graph filter decomposition, c.f. Fig. (left.. The model provides unified framework

---

Published as a conference paper at ICLR 2021
ta)
X
Mad (nd.e) ol.
Figure 1: (a) K-rank graph local filters. Notation as in Sec. 2.1 and specifically, u is node index, is channel index, basis index, and learnable local basis B3 comhined by learnable coefficients dg- (b) The first two figures shows the good property landmarks for being invariant pose and built on facial landmarks.
number basis. M is the
the GNN linear mapping []] [ decomposed into
viewpoint changes. The third figure illustrates the graph
for graph convolutions, including ChebNet (Defferrard al. 2016), GAT, EdgeNet [Isufi jet al. 2020) and CNN/geometrical CNN with low-rank filter as special cases. In addition, theoretically prove that L3Net is strictly more expressive to represent graph signals than spectral graph convolutions based on global adjacency /graph Laplacian matrices, which is then empirically validated, c.f. Sec. 3..1 We also prove a Lipschitz-type representation stability of the new graph convolution layer using perturbation analysis.
Because our model allows neighborhood specialized local graph filters, regularization may be needed to prevent over-fitting, so as to handle changing underlying graph topology and other graph noise, e.g., inaccurately detected landmarks or missing landmark points due to occlusions, Therefore, we also introduce regularization scheme based on local graph Laplacians, motivated by the eigen property of the latter. This further improves the repre- sentation stability aforementioned. The improved performance of L3Net compared to other GNN benchmarks is demonstrated in a series of experiments, and with the the proposed graph regularization, our model shows robustness to a variety of graph data noise.
In summary, the contributions of the work are the following:
We propose a new graph convolution model by a low-rank decomposition of graph filters over trainable local basis, which unifies several previous models of both spec- tral and spatial graph convolutions.
Regularization by local graph Laplacians is introduced to improve the robust.ness against graph noise.
We provide theoretical proof of the enlarged expressiveness for representing graph signals and the Lipschitz-type input-perturbation stability of the new graph convo- lution model.
We demonstrate with applications to object recognition of spherical data and facial expression pnrressoonsskleeoonn-o /skeleton-baset action recognition using landmarks. Model robustness against graph data noise is validated on both real-world and simulated datasets.
1.1 RELATED WORKS
Modeling on face body landmark data. Many applications in computer vision, such as facial expression recognition (FER) and skeleton-based action recognition, need to extract high-level features from landmarked data which are sampled
irregular grid points on
human face or at body joints. While CNN methods (Guo et al. 2016 Ding et al. 2017 Meng al. 2017) prevail in FER task, landmark methods have the potential advantage in lighter model size as well as more robustness to previously mentioned geometric transformations like pose variation. Earlier methods based facial landmarks used hand-crafted fcatures (Jeong & Ko 2018 Morales- Vargas et al.) 2019) rather than deep networks. Skeleton based methods in action rccognition have been developed intensively recently (Ren et al.] (2200) including non-doep methods /Vemulapalli et al.
2014b Wang al. 2012) and deep methods (Ke et al. 2017 Kim & Reiter] [011]] Liu et al. 2016 Yan et al.) 2018). Facial and skeleton
landmarks only give coarse and irregular grid, and then mesh- geometrical CNN's are hardly applicable, while previous GNN models on such tasks may lack sufficient expressive power.
Graph convolutional network. A systematic review can be found in several places, e.g. Wu et al. (2020). Spectral graph convolution was proposed using full eigen decomposition of the graph Laplacian in BBunn et. al. (2013), Chebyshev polynomial in ChebNet. (Defferrard
2

---

Published as a conference paper at ICLR 2021
et al. 2016); ; by Cayley polynomials in Levie et al. 2018 GCN (Kipf & Welling 2016
The mostly-used GÑN, is a variant of ChebNet using degree-1 polynomial. Liao el al.
(2019) accelerated the spectral computation by Lanczos algorithm.
Graph scattering
transform has been developed using graph wavelets (Zou & Lerman 2020
Gama al.,
2019b), which can be constructed in the spectral domain (Hammond et al. 2011 and by
dittuston wavelets (Coifman & Maggioni] 2006). The scattering transtorm enjoys theoretical properties of the representation but lacks adaptivity compared to trainable neural networks. Spatial graph convolution has been performed by summing up neighbor nodes' transformed features in NN4G (Scarselli et al. 2008), by graph diffusion process in DCNN (Atwood & Towsley 2016), where the graph propagation across nodes is by the adjacency matrix. Graph convolution with trainable filter has also been proposed in several settings: MPNN
Giimer et al. 2017) enhanced model expressiveness by message passing and sub-network; GraphSage (Hamilton et al. 2017) used trainable differential local aggregator functions in the form of LSTM or mean max-pooling: GAT (Veličković et al. 2017) and variants (Li
ct al. 2018 Zhang et al.) 2018 Liu et al., 2019) introduced attention mechanism to achieve adaptive graph afhniiy, which remains non-negative valued; EdgeNet (Isufi et al. 2020) developed adaptive filters by taking products of trainable local filters. Our model learns local filters which can take negative values and contains GAT and EdgeNet as special cases.
Theoretically, expressive power of GNN has been studied in Morris et al. (2019); Xu et al. (2019); Maron et al. (2019a b); Keriven & Peyré (2019), mainly focusing on distinguishing graph topologics, while our primary concern is distinguish signals lying on a graph.
CNN and geometrical CNN. Standard CNN applies local filters translated and shared across locations an Euclidean domain. To extend CNN to non-Euclidean domains, convo- lution on a regular spherical mesh using geometrical information has been studied in S2CNN (Cohen et al. 2018). SphereNet (Coors el al.] 2018), SphericalCNN (Esteves el al. 2018 and UGSCNN (Jiang et al., 2019), and applied to 3D object recognition, for which other deep methods include 3D convolutional 'Qi et al., (0166) and non-convvlutional architec- tures (Qi et al. 2017a bj. CNN's on manilodds construct weight-sharing across local atlas making use of a mesh e.g.. by patch operator in Masci et al. (2015), anisotropic convolution 2016), mixture model parametrization in MoNet (Monti et al. SplineCNN (Fey et al. 2018). and manifold parallel transport in Schonsheck et al. (2018). These geometric CNN models use information of non-Fuclidean meshes which usually need sufficiently fine resolution.
in ACNN (Boscaini et al.
2017 20liiespline functions
2 METHOD
2.1 DECOMPOSED LOCAL FILTERS
Consider an undirected graph G = EV,
= |V|= A graph convolution layer maps from
imput node features X(u', c²) to output Y(u,c), where u, u' E V, d' E [C'] (c e (C]) is the input (oulput) channel index, the notation [m] means {I,..., m], and
((u,c)= =0
Σ WEV
M(,', ((u,,, + bias(c)), uEV,
(1)
The spatial and spectral graph convolutions correspond to different ways of specifying M, c.f. Sec. 2.3 The proposed graph convolution is defined as
M(,' u, c.) = Σ c B)('') u)), ag(c', ER,
(2)
where Ba(u', u) is non-zero only when u' E N((d)) N((d) denoting the d-th order neighborhood of u (i.e., the set of neighbbss of u), and K is a fixed number. In other words, B 's are
K basis of local filters around each u, and the order da can diller with S k < K. Both ag and Bş are trainable, so the number of parameters are K CC + E Evev [v(d)
K- CC' + K Knp, where p stands for the average local patch size. In our experiments we use K up to 5, and dy up to 3. We provide the matrix notation of (2 in Appendix A.1
The const ruction 2 can be used as layer lype in larger GNN archilectures. Pooling of graphs can be added between layers, and see Appendix C.5 for further discussion on multi-
scale model. The choice of K and neighborhood orders (di.-.., .......,de dk) can also be adjusted accordingly. The model may be extended in several ways to be discussed in the last section.
3

---

Published as a conference paper at ICLR 2021
(b)
10
Model ChebNet, GCN GAT EdgeNet Low-rank CNN
#params
LOC" CO"
4afs1)
4afy3)
R(CC' + 20)
LÍCC" + up ())
2286
Ag
K(CC' + p))
Locally-conuected
CC' np
Loe D- A No.
L3Net
KICC' + ap)
Figure 2: Plots: (a) Local graph Laplacian Lu := D- A neighborhood around node u. (b) Plots of the Dirichlet cigenvectors on the local graph. The first Dirichlet cigenvector does not change sign on N₂ and envelope- like.. (Table) Model complexity measured by number of parameters, C' and C' being the number of imput and output channels, p (p()) the average patch size of local neighborhoods (local 1-neighborhoodss, more in Sec. 2.3
2.2 REGULARIZATION BY LOCAL GRAPH LAPLACIAN
The proposed T.3Net layer enlarges the model capacity by allowing K basis filters at each location, and natural way to regularize the trainable filters is by the graph geometry, where, by construction, only the local graph patch concerned. We introduce the following regularization penalty of the basis filters Bg 8 as
K
R((Baba) = Σ Σ
L
(0) = Ba(u, 6(0) N(de) - R,
(3)
where (R) equaling (D)
A) restricted to the subgraph on Ndde), is the Dirichlet local The training objective is
graph Laplacian on (((d)) Chung & Graham 1997) (Fig. 2
[((ax, B&]x) + XR((B&)*), A
where L is the classification loss. As L encourages the diversity of B 8. the K-rankness usually remains a tight constraint in training, unless À is very large, see also Proposition
2.3 A UNIFIED FRAMEWORK FOR GRAPH CONVOLUTIONS
Graph convolutions basically fall into two categories, the spatial and spectral constructions (Wu et al. 2020 The proposed L.Nett belongs to spatial construction, and here we show that the model (2 is a unified framework for various graph convolutions, both spatial and spectral. Details and proofs are given in Appendix A
ChebNet (Defferrard al. 2016), GAT (Veličkovié et al. 2020 In Cheb.eet M per (c,, cc) equals a degree-(L-I) polynomia
2017 EdgeNet [sufi et al.
the graph Laplacian matrix, where the polynomial coefficients are trainable. GCN (Kipf & Welling 2016) can be viewed as ChebNet with polynomial degree-1 1 and tied coefficients. The attention mechanism in GAT enhances the model expressiveness by incorporating adaptive kernel-based non- negative affinitics. In EdgeNet, the graph convolution operator is the product of trainable local filters supported on order-1 neighborhoods. We have the following proposition:
Proposition 1. L9Net (2) includes the following models as special cases:
(1) ChebNet (GCN) when K > L (K 2 2), L being the polynomial degree.
(2) GAT when K 2 R, being the number of attention branches.
(3) EdgeNet when K 2 L, L being the order of graph convolutions.
CNN: When nodes lie on a geometrical domain that allows translation (w'uu), in 2 setting Ba (u', u) = (u -u) for some (-) enforces spatial convolutional. The convolutional kernel can be decomposed mesh is also possible as in Masci et al. (2015]; Fey et al. (2018). We have the following:
Σ ax,(", (.b, (Qiu et al.] 2018h. Extension to CNN manifold
Proposition 2. Mesh-bosed geometrical CNN's defined by linear patch operators, including standard CNN on IRd, and with low-rank decomposed filters are special cases of L3Net (2)
We also note that L3Net reduces from locally connected GNN (Coates & Ng 2011 Bruna el al. 2013). the largest class of spatial GNN, only by the low-rankness imposed by a small number of K in (2) Locally connected GNN can be viewed as (1) with the requirement that for each (c, c.), Mu', u; c'.')c) is nonzero only when u' is locally connected in The complexities of the various models are summarized in Fig. 2 (Table), where L3Net reduces from the np. CC' complexity of locally-connected net to be the additíve (np+ CC') times K.
4

---

Published as a conference paper at ICLR 2021
When the number of channels C, C' are large, e.g. in deep layers they 102, and the graph size not large, e.g,, landmark data applications up & CC", the complexity dominated by KCC" which is comparable with ChebNet (GAT) if K ~ L (R). The computational cost also comparable, as shown in experiments in Sec. Furthermore, we have:
(d(d)) are all connected, given Ou, > for all u, k, the minimum of 3 with constraint [lb] ll2 2 au,k is achieved when b(²) equals the first Dirichlel eigenveclor on N(dd), which does nol change sign on N((d))
Proposition 3. Suppose the subgraphs
The proposition shows that in the strong regularization limit of X + oo in L3Net reduces to be ChebNet-like. The constraint with constants au,k is included because otherwise the minimizer will be B₁ all zero. The first Dirichlet eigenvector is envelope-like (Fig. [ and then Ba(,,u, u) will be averaging operators on the local patch. Thus the regularization parameter À can be viewed as trading-off between the more expressiveness in the learnable BR, and the more stability of the averaging local filters, similar to ChebNet and GCN.
ANALYSIS
We analyze the representation expressiveness and stability (defined in below) of the proposed L.Net model. All proofs in Appendix A and experimental details in Appendix B
3.1 REPRESENTATION EXPRESSIVENESS OF GRAPH SIGNALS
The theoretical question graph signal representation expressiveness concerns the ability for GNN deep features to distinguish graph signals. While related, the problem differs from the graph isomorphism test problem which has been intensively studied in the GNN expressiveness literature. Here we prove that L3Net is strictly more expressive than certain spectral GNNs, and support the theoretical prediction by experiments.
We have shown that the L3Net model contains ChebNet (Proposition [ and the following proposition proves the strictly more expressiveness for graph signal classification. We call B a graph local filter if B(u, v) is non-zero only when e is in the neighborhood of u. In a spectral GNN, the graph convolution takes the form as x + f(A)z where f is function on R. and A the (possibly normalized) adjacency matrix.
Proposition 4. There is graph and 1) A local filter B on it such that B cannot be expressed by any spectral graph convolution, but can be expressed by L3Net with K 1. 2) Two data distributions on the graph (two classes) such that, with permutation group invoriant operator the last layer, the deep feature of any spectrol GNN cannot distinguish the two classes, but that of L3Net with 1 loyer and K == can.
The fundamental argument is that spectral GNN is permutation equivariant (see e.g. Gama el al. (2019a), reproduced as Lemuna A. , and the local filters in L3Net break such symmetry to oblain more discriminative power. The constructive example used in the proof is on a ring graph (Fig. A.1 A and the basis B), and the two data distributions shown in Fig. 3 Proposition 4 gives that, on the ring graph and using GNN with a global pooling in the last layer, an L.NNet layer with K = can have classification power while ChebNet with any order cannot. On chain graph (removing the connection between two end points in a ring graph), which not exactly follows the theory assumption, since the two graphs only differ at one edge, expect that it will remain a difficult
for the ChebNet but not for L3Net. To verify the theory, we conduct experiments using a two-layer GNN and the results are in Fig. 3 (table). In the last row, we further impose shared basis across nodes which
Model
order
#parnms u.sk
graph Ace
chaim Are
L-3
51305 =.33
(b)
1.0
1.2
ChehNet
L-6
10.7k
0.24
51,07 0:37
+ 0.41
0.1
$1.03
00:
(R-8)
10.4k
57.82
8.06
58.04 9.13
WIN
4.5k
1 0.50
518 0.08
0.2
MPNN
9.4k
2.76
50:32 + 0.05
51.00 1 11.12
1000 = 0.08
M13t = 100
0.0
20 40
60
LSNet
0:1:2
7.4k
2.5k
99.96 1 0.01
09.00 1 0.03
99.94
99.85 0.04
0.01
Pigure 3: Up/down-wize classiftcation. Plots: (a) Example data from two classes. (b) Learned shared basis on
table. (Table) Test accuracy by MPNN (Gilane et aL. (2017) WLN (Morris et al. 2019). ChebNet up to L=30 and LäNet K=1 and 3, as well as GAT with diflerent Last order
the graph neighborhood 3. corresponding the last row
L3Net with shared basis B(-, u) all locations u.
5

---

Published as a conference paper at ICLR 2021
reduces L3Net to a 1D convolutional layer, and the learned basis shows "difference" shape (right plot) which explains its classification power. Results are similar using a 1-layer GNN (Tab. A.1. The argument in Proposition 4 extends to other graphs and network types. Generally, when a GNN based on global graph adjacency or Laplacian matrix applies linear combinations of local averaging filters, then certain graph filters may be difficult to express. We experimentally examine GAT, WLN and MPNN, which underperform the binary classification task, as shown in Fig. 3 (table).
3.2 REPRESENTATION STABILITY
We derive perturbation bounds of GNN feature reprosentation, which is important for bustness against data noise. The analysis implics a trade-off between de-noising and keeping high-frequency information, which is consistent with experimental observation in Sec. |
Consider the change in the GNN layer output defined in ( (2) when the input X changes. For simplicity, let. C = C' = 1, and the argument extends. For any graph signal x V - IR and V C V. define || := (Euevi x( (())))1/2 and (r.y)v v = Lnev z(u)y(u). The following perturbation bound holds for the L3Net layer with/ without regularization.
Thcorem 1. Suppose that X = (X(u))uev is perturbed to be X -X+AX the activation
function a R + R is non-expansive, and supuEv Σ [AV(dW)) S Kp, then the change in the output {Y(u))uEV in 2-norm is bounded by
| S 8() (all//ppAXXlll
8()) == sup | 1) 2.
k,a
Note that p indicates the averaged size of the dg-order local neighborhoods. The proposition implics that when K is (1), and the local basis By's R have O(1) 2-norms all local parches uniformly bounded by g(), then the Lipschitz constant of the GNN layer mapping is O(1), ie., the product of ||a||2, g(2) and VKp, which does not scale with n. This resembles the generalizes the 2-norm of convolutional operator which only involves the norm of the convolutional kernel, which is possible due to the local receptive fields in the spatial construction of L3Net.
The local graph regularization introduced in Sec. 2.2 improves the stability of Y w.r.t. AX by suppressing the response to local high-frequency perturbations in AX. Specifically, the local graph Laplacian I!(h) on the subgraph on N. is positive definite whenever the subgraph is connected and not isolated from the whole graph. We then define the weighted Ni
2-norm on local patch || 1 == (z, L 2) (da), and similarly ||<)|(c)?))-
Theorem 2. Notation and setting as in Theorem 1 if furtherly, all the subgraphs on Ni(de) are connected within itself and to the rest of the graph, and there is p 0 s.t. Vu, k; ||AX| | )- S A ll, (,, then
AY S pg(2) ||alll Ap AX 2,V, == [B u) 111g. k.u
The bound improves from Theorem 1 when p0(2) g(1,, and regularizing by R En,e [Ba, w) Illl? leads to smaller ((2)_ Meanwhile, on each N((d2) the Dirichlet eigenval-
ues increases < Ai S A2.... S Apc.es Pu,E == |N!d))) thus weighting by X in || ) decreases the contribution from high-frequency cigenvectors. As a result, P will be small if AX contains significant high-freyuency component on the local patch, e.g., additive Gaussian noise or missing values. Note that in the weighted 2-norm of AX by (1) only the relative amount of high-frequency component. in AX matters (because any con- stant normalization of (8) cancels in the product of p and 3(2)). The benefits of local graph regularization in presence of noise in graph data will be shown in experiments.
4
EXPERIMENT
We test the proposed L3Net model several datasets Codes available at http://gtttuubccooo//cceeeaaaaie TT.Net

---

Published as a conference paper at ICLR 2021
Model
4:3,2
3:2:
3:2:0
2:2,1
2:1:0
3:000
2:0;0
Acc
Acc
Acc
Aoe
Aoc
Acc
Acc
Acc
UGSCNN
99.2
985 S1
97.52
97. 97.96
98. 22
97.
75.75
86.61
GCN
90.46
27. 97.92
37.07
ChebNet
99.3
98, 50
98.0 08.07
97.07
97. 12
95.51
73.1
90.73
level 2
level
LaNet (1:1:2:3)
98.81
97.76
97.97
97.26
Figure 4: (Plot) Teosahedral spherical meshes at level 2 and 1. (Table) Testing accuracies of sphere MNIST level in GNN layer. LäNet uses K=4,, (Cohen et al. 2018) mesh (4;3:2) has accuracy 96.0.
under different mesh settings, (21; stands for
neighborhood order (1:1;2;3). S2CNN
4.1 OBJECT RECOGNITION OF DATA ON SPHERICAL MESH
We first classify data & spherical mesh: sphere MNIST and sphere ModelNet-40, following the settings in literature. Though regular mesh on sphere is not the primary application scenario that motivates our model, we include the experiments to compare with benchmarks and test the efficiency of L3Net such regular meshes. Following UGSCNN (Jiang al. 2019), we implement different mesh resolution on a sphere, indicated by "mesh level" (Fig. 40, where number of nodes in different levels vary from 2562 (level 4) to 12 (level 0). All The networks consist of three convolutional layers, see more details in Appendix C.1 Using the original mesh level (4:3:2), the finest resolution as in UGSCNN, L3Net gives among the best accuracies for sphere MNIST. On Modelnet-40, L3Net achieves testing accuracy of 90.24, outperforming ChebNet and GCN and and is comparable to UGSCNN which uses spherical mesh information (Tab. A.2)) When the mesh becomes coarser, shown in Fig. 4 (Table), L3Net improves over GCN and ChebNet (L=4) and is comparable with UGSCNN under nearly all mesh settings. We observe that in some settings ChebNet can benefit from larger I, but the overall accuracy still inferior to L3Net. The most right two columns give two cases of coarse meshes where L3Net shows the most significant advantage.
4.2 FACIAL EXPRESSION RECOGNITION (FER)
We test on two FER datasets, Extended CohnKanade (CK+) [uccy el al., 2010 and FER13 (Goodfellow et al., 2013). We use 15 facial landmarks, see Fig. D and pixel values on a patch around each landmark point as node features. Details about dataset and model setup in Appendix C.2 Unlike spherical mesh, facial and body landmarks
coarse applicable. We benchmark
irregular grids where no clear pre-defined mesh operation L3Net with other GNN approaches, as shown in Table [] The local graph regularization strategy is applied on FER13, due the severe outlier data of landmark detection caused by occlusion. On CK+, L3Net leads all non-CNN models by a large margin, and the best model (1,1,233) uses comparable number of parameters with the best ChebNet (L=4). On FERI3, L3Net has lower performance than ChebNet and EdgeNet (Isufi et al. 2020 but outperforms after adding regularization. The rumning times of best ChebNet and L3Net models are comparable, and are much less than GAT's.
CNN# Guo et al. 2010 landmark method using handcrafted features MMoaless Vargas et 2019 and various methods. Specihcally, we compare to GAT (Velickovié et sl. 2017) with different #heads (b) and #features (f). The mean testing time
Table 1: Results CK+ and FER13, with comparison to CNN' Ding al. 2017
CK+: ChebNet (I=4) 4) 12.00mm, LoNet forder 1,1,2,3) 13.02ma. GAT (h=f=8) 39.67ms, (h=f= 16) 41.02ms.
CK+
FER13
Model
Bases Order
#params (w/o FC)
Ace
(w/o FC)
#params
Acc
CNNT
7M
98.60
CNNT. Landmarks-handee
2.6M
71.33
91.00
0.03
GAT (h=8, f=8)
1
31.6k
91.62 + 1.16
46.9k
49.50
GAT' (b=16, f=16)
142.3k
151.1k
GCN
1
31.5k
91.78
+ 0.38
42.6k
55.54
GraphConv
169.6k
81.62
0.48
215.4k
55.63
1.33
102.3k
92.93 1: 0.59
136.4k
59.68
ChebNet
L=4
0.37
1.=5
170.2k
93.03 1: 0.62
227.3k
60.29
EdgeNet
103.4k
92.41 + 0.8T
137.2k
58.73
1.=4
137.1k
92.57 1: 0.84
182.5k
60.05
2:2:2
102.8k 8k
95.32 + 0.31
139.7k
60.46
0:1:2:3
136. 83
95.03 - 0.30
182.8k
60.65
L3Net
1:1:2
102.7k
94.68 + 0.56
139.4k
59.68
+reg0.005
9-1.52 - 0.61
61.13
1;1:2,3
95.37 0.60
60.71
13G. 13k.9k
183.0k
+reg0.5
95.11 = 0.14
61.64
7

---

Published as a conference paper at ICLR 2021
Table 2: Results NTU-RGB+D and Kinetics-Motion
NTU-RGB+D
Kinelics- Motion
Model
Bases order
# parrmss (w/o PC)
x-view Acc
x-sub Acc
#params (w/o FC)
Acc
ST-GON Yan et al 2018
88.30
81,50
72.4
ST-GON
2.6M
82.39
74.33
1.4M
72.85
L-3
3.1M
86.40
78.24
1.8M
77.91
S1-ChebNet
L=4
3.3M
86.45
80.20
2.1M
78.2
1=55
3.5M
76.70
71.42
2.3M
77.57
1:122
90.78
83.64
75.20
3.1M
1.8M
ST-L3Net
+reg0.01
88.38
81.54
78.49
+reg0.01
1:::2:3
3.3M
91.52
89.87
82.46
80.97
2.1M
76.68
76.07
4.3 ACTION RECOCNITION
We test on two skeloton- based action recognition datasets, NTU-RGB+D (hhhhoouyy et al. 2016) and Kinetics-Motion (Kay et al. 2017). The irregular mesh is the 18/25-point body landmarks, with graph edges defined by body joints, shown in Fig. [ and Fig. A.2 We adopt ST-GCN (Yan et al.) 2018) as the base architecture, and substitute the GCN layer with new L3Net layer, called L3-e.. On Kinelics-
adopt the regularization mechanism to overcome the severe data missing caused by camera out-of-view. See more experimental details in Appendix C.3 We benchmark performance with ST-GCN (Yan el. al. 2018), ST-GCN (our implementation without using geomet information) and ST- ChebNet (replacing GCN with ChebNet layer), shown in Table 2 L3Net shows significant. advantages on two NTU tasks, cross view and cross-subject settings. On Kinetics- Menetics-Motion, Motion, L.3Net. regains superiority over other models after applying regularization. The results in indicate that stronger regularization sacrifices expressiveness for clean data and gains stability for noisy data, which consistent with the theory in Sec. 3.2
both Table [ and 2
4.4 ROBUSTNESS TO GRAPH NOISE
To examine the robustness to graph noise, we experiment on down-sampled MNIST data on 2D regular grid with d-nearest-neighhoo graph. With no noise, on 28 28 data (Tab. A.3 14x14 data (Tab. A.4), and 7x7 data (Tab. "original" column), the performance of L3Net is comparable to ChebNet (Defferrard et al.) 2016)) and EdgeNet (Isufi et al. 2020) and better than other GNN methods. We consider three lypes of noise, Gaussian noise added the pixel value, missing nodes or equivalently missing value image input, and permutation of the node indices, details in Appendix C.4] The results of adding different levels of gaussian noise and permutation noise are shown in Tab. B while results of adding missing value noise is provided in Appendix C.4. The results show that our regularization scheme improves the robustness to all three types of graph noise, supporting the theory in Sec. 3.2 Specifically, L3Net without regularization may underperform than ChebNet, but catches up after adding regularization, which is consistent with Proposition
Table 3: Resulta on MNIST with grid size 7 with different levels of Gaussian noise and Permutation noise.
Model
bases order
#params (w/o FC)
Acc(original)
Acc (gaussian) (ponr 24.9)
Acc (gaussian) [perr 19.1)
Acc (gaussian) [pear 15.7)
Ace [permatation)
GON
M0.02 1 0.24
80 0.00
85.70 0:13
81.32
85.00
Lm3
6.5k
32.85 2 0.00
01.13 = 0.15
87.04 0.23
82.70 = 0.33
80.34 = D.D0
ChebNet
L=5
10.7k
93.2 1 0.07
91.92 1 0.11
88.22 1. 0.10
83.04 1. 0.12
87.27 0.23
L
14.8k
98.45 + 0.06
91.80
0.10
87.84 0.15
83.76 + 0.14
87.58 0.19
GAT (k=8,(=16)
17.3k
79.50 1 1.24
68.68
0.45
64.8 1.89
65.38
1.03
62.21 0.56
MPNN
86.04
83.30
0.35
77.59 0.33
71.35
WLN
1k
87.01 1 0.00
86.01
0.20
83.00
0.00
70.47
0:11
80.51
0.005
EdgeNet
L=4
10.1k
7.5k
93.44
03.26 2 0.16
1 0.17
92.27
01.81
1 0.16
0.14
88.60
85.42
1. 0.17
0.36
84.58
84.15 1 0.59
0.400
87.44 1 0.28
87.15 1111::200 0.30
0:122
8.1k
03.45 1 0.10
L8Net
4-w00.5
8.4k
31.300
0.08
58.201 0.15
23
84.59
53.00 0.35
23
1::2:33
90.07 =
0.16
82.80
0.37
8T.00
+.eg0.5
93.85 1 0.15
82. 56
0.12
89. 0.24
84.61 1: 0.00 0.25
88.21 0.15
5 CONCLUSION AND DISCUSSION
The paper proposes a new graph convolution model using learnable local filters decomposed over small number of basis. Strengths: Provable enhancement of model expressiveness with significantly reduced model complexity from locally connected GNN. Improved sta- bility and robustness via local graph regularization, supported by theory. Plug-and-play layer type, suitable for GNN graph signal classification problems on relatively unchang-
8

---

Published as a conference paper at ICLR 2021
ing small underlying graphs, like face/body landmark data in FER and action recognition applications.
Limitations and extensions: (1) Scalability to larger graph. When [V] n is large, the complexity increase in the rip term would be significant. The issue in practice remedied by mixing use of layer types, e-g., only adopting L3Net layers in upper levels of mesh which are of reduced size. (2) Dynamically changing underlying graph across samples. the underlying graph, we can benefit from solutions such as node registration or other preprocessing techniques, possibly by another neural network. Related the question of reducing model dependence on graph topology, possibly under statistical model of the underlying graphs. This includes transferability to larger networks. (3) Incorporation of edge features. Edge features can be transformed into extra channels of node features by an additional layer in the bottom, and the low-rank graph operation can be similarly employed there. (4) Theoretically, the representation robustness analysis to be extended to more general types of graph perturbation. Generally, one can work to extend to other types of graph data and tasks.
be
For more severe changes
ACKNOWLEDGEMENTS
The work is supported by NSF (DMS-1820827). XC is partially supported by NIH and the Alfred P. Sloan Foundation. ZM and QQ are partially supported by NSF and the DARPA TAMI program.
REFERENCES
James Atwood and Don Towsley. Diffussion-convolutiinaal neural networks. In Advances in newral information processing systems, pp. 2000, 2016.
John R. Baungardner and Paul O Frederickson. Icosahedral discretization of the two-sphere. SIAM Journal on Numerical Analysis, 2207)11077 1985.
Davide Boscaini, Jonathan Masci, Emanuele Rodolå, and Michael Bronstein. Learning shape correspondence with anisotropic convolutional neural networks. In Advances in neural information processing systems, pp. 3189 -197,,1977110 2016.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18 1221188-22220 2017.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXi::1312 6203, 2013.
Adrian Bulat and Georgios Tzimiropoulos. How far are we from solving the 2d & 3d face alignment problem? (and a dataset of 230,000 3d facial landmarks). In International Conference on Computer Vision, 2017.
Zhe Cao, Tomas Simon, Shih-En Wei, and Yaser Sheikh. Realtime multi-person 2d pose estimation using part affinity ficlds. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 7291 7299, 2017.
Dong Chen, Xudong Cao, Fang Wen, and Jian Sun. Blessing of dimensionality: High- dimensional feature and its efficient compression for face verification. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 3025 3032, 2013.
Fan RK Chung and Fan Chung Graham. Spectral groph theory. Number 92. American Mathematical Soc., 1997.
Adam Coates and Andrew Y Ng. Selecting receptive fields in deep networks. In Advances in neural information processing systems, pp. 2528 2536, 2011.
Taco S Cohen, Mario Geiger, Jonas Köhler, and Max Welling, Spherical cnns. arXiv preprint X 10o: 100.100130, 2018.

---

Published as a conference paper at ICLR 2021
Ronald R Coifman and Mauro Maggioni. Diffusion wavelets. Applied and Computational Harmonic Analysis, 21))):53 94, 2006.
Benjamin Coors, Alexandru Paul Condurache, and Andreas Geiger. Spherenet: Learning spherical representations for dctection and classification in omnidiroctional images. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 518-533, 2018.
Timothy F. Cootes, Gareth J. Edwards, and Christopher J. Taylor. Active appearance models. IEEE Transactions on pattern analysis and machine intelligence, 23(6):681 685, 2001.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural net- works on graphs with fast localized spectral filtering, In Advances neural information processing systems, pp. 3844 3852, 2016.
Hui Ding, Shaohua Kevin Zhou, and Rama Chellappa. Facenet2expnet: Regularizing deep face recognition net for expression recognition. In 2017 12th IEFE Indernational Conference on Automatic Face & Gesture Recognition (FG 2017), pp. 2017.
IEEE,
Carlos Esteves, Christine Blenn-Blacchete, Ameesh Makadia, and Kostas Daniilidis, Learn- ing so (3) equivariant represenlations with spherical cmns. In Proceedinggs of the European Conference on Computer Vision (ECCV), pp. 52 68, 2018.
Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller. Splineenn: Fast geometric deep learning with continuous b-spline kernels. In Proceedings of the IEEE Conference on Computer Vision and Pullern Recognition, pp. 869 877, 2018.
Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks. arXiv preprint arXiv:1905004533 2019a.
Fernando Gama, Alejandro Ribeiro, and Joan Bruna. Diffusion scattering transforms on graphs. In International Conference on Learning Representations, 2019b.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning-Volle Volume 70, pp. 1263-1272. JMLR. org, 2017.
Tan J Goodfellow, Dumitru Erhan, Pierre Lue Carrier, Aaron Courville, Mehdi Mirza, Ben Hamner, Will Cukierski, Yichuan Tang, David Thaler, Dong-Hyun Lee, et al. Challenges in representation learning: A report three machine learning contests. In International Conference on Neural Information Processing, pp. 117-124. Springer, 2013.
Yanan Guo, Dapeng Tao, Jun Yu, Hao Xiong, Yaolang Li, and Dacheng Tao. Deep neural networks with relativity learning for facial expression recognition. In 2016 IEEE Inter- national Conference on Multimedia & Expo Workshops (ICMEW), pp. 1-6. IEEE, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pp. 1024 1034, 2017.
David Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129-150, 2011.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pottern recognittion, pp. 770-778, 2016.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 4700 4708, 2017.
Elvin Isufi, Fernando Gama, and Alejandro Ribeiro. Edgenets: Edge varying graph neural networks. or Xio preprint arXi:22001.07620, 2020.
10

---

Published as a conference paper at ICLR 2021
Mira Jeong and Byoung Chul Ko. Driver's facial expression recognition in real-time for safe driving. Sensors, 18(12):4270, 2018.
Chiyu Jiang, Jingwei Huang, Karthik Kashinath, Philip Marcus, Matthias Niessner, et al. Spherical cnns unstructurod grids. arXiv preprint orx:i:1901 00000.00099, 2019.
Will Kay, Joao Carreira, Karen Simonyan, Brian Zhang, Chloe Hillier, Sudheendra Vijaya- narasimhan, Fabio Viola, Tim Green, Trevor Back, Paul Natsev, et al. The kinetics human action video dataset. arXiv preprint trXiv:1705.0690 2017.
Qiuhong Ke, Mohammed Bennamoun, Senjian An, Ferdous Sohel, and Farid Boussaid. A new representation of skeleton sequences for 3d action recognition. In Proceedings of the TEEE conference on computer vision and pattern recognition, pp. 9288-32977 2017.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural net- works. In Advances in Neural Information Processing Systems, pp. 7090-7099, 2019.
Tae Soo Kim and Austin Reiter. Interpretable 3d human action analysis with temporal con- volutional networks. In 2017 IEEE conference on computer vision and pattern recognition workshops (CVPRW), pp. 1-23-1631. IEEE, 2017.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional nelworks. Xiv preprinl ar 1rxiv:16099000 02907, 2016.
Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Transactions Signal Processing, 611:97771 2018.
Ruoyu Li, Shong Wang, Feiyun Zhu, and Junzhou Huang. Adaptive graph convolutional neural networks. In Thirty-second AAAI conference on artificial intelligence, 2018.
Shan Li and Weihong Deng. Deep facial expression recognition: A survey. IEEE Transac- tions on Affective Computing, 2020.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. ICLR, 2019.
Jun Liu, Amir Shahroudy, Dong Xu, and Gang Wang. Spatio-temporal Istm with trust gales for 3d human action recognition. In European conference compuler vision, pp. 816 833. Springer, 2016.
Ziqi Liu, Chaochao Chen, Longfei Li, Jun Zhou, Xiaolong Li, Le Song, and Yuan Qi Geniepath: Graph neural networks with adaptive receptive paths. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4424 4431, 2019.
Patrick Luccy, Jeffrey F Cohn, Takeo Kanade, Jason Saragih, Zara Ambadar, and Iain Matthews. The extended cohn-kanade dataset (ck+): A complete dataset for action unit and emotion-specified expression. In 2010 ieee computer society conference on computer vision and pattern reognittinn-workshopg pp. 94-101. IEEE, 2010.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, pp. 2153 2164, 2019a.
Haggai Maron, Heli Ham-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivari- ant graph networks. 2019b.
Jonathan Masci, Davide Boscaini, Michael Bronstein, and Pierre Vandergheynst. Geodesic convolutional neural networks on riemannian manifolds. In Proceedings of the IEEE in- ternational conference computer vision workshops, pp. 37-45, 2015.
Zibo Meng, Ping Liu, Jie Cai, Shizhong Han, and Yan Tong. Identity-awanl aware convolutional neural network for facial expression recognition. In 2017 12th IEÉE International Con- ference A Aulomatic Face & Gesture Recognition (FG 2017), pp. 558 565. IEFF, 2017.
11

---

Published as a conference paper at ICLR 2021
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cmns. In Proceedings of the IEEE Conference on Computer Vision and Pottern Recognition, pp. 5115 5124, 2017.
E Morales- Morales-Vargas, CA Reyos-Garefa, and Hayde Peregrina-Barrete On the of action units and fuzzy explanatory models for facial expression recognition. PloS one, 14(10), 2019.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the A AAAT Conference on Artificial Intelligence, vol- ume 33, pp. 4602 4609, 2019.
Charles R Qi, Hao Su, Matthias Nicßner, Angela Dai, Mengyuan Yan, and Lconidas J Guibas. Volumetric and multi-view cmns for object classification on 3d data. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5648 5656, 2016.
Charles Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. Tn Proceedings of the IEEF conference on computer vision and pattern recognition, pp. 652-660) 2017a.
Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas Guibas. Pointnet++:: Deep hierar- chical feature learning on point sets in a metric space. In Advances in neural information processing systems, pp. 5099-5108, 2017b.
Q Qiu, X Cheng, R Calderbank, and G Sapiro. Defnet: Deep neural network with decom- posed convolutional filters. In International Conference Machine Learning, 2018.
Anurag Ranjan, Timo Bolkart, Soubhik Sanyal, and Michael J Black. Generating 3d faces using convolutional mesh autoencoders. In Proceedings of the European Conference on Compuler Vision (ECCV), pp. 704-720, 2018.
Bin Ren, Mengyuan Liu, Runwei Ding, and Hong Liu. A survey on 3d skeleton based action recognition using learning method. arXiv preprint xrv:22000.00500 2020.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Mon- fardini. The graph neural network model. IEEE Trunsuctions on Neural Networks, 20(1): 61-80, 2008.
Stefan C Schonsheck, Bin Dong, and Rongjie Lai. Parallel transport convolution: A new tool for convolutional neural networks manifolds. arXiv preprint arXiv:1805.078.0 2018.
Amir Shahroudy, Jun Liu, Tian-Tsong Ng, and Gang Wang. Ntu rgb+ d: A large scale dataset for 3d human activity analysis. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1010 1019, 2016.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiw:1110.10000 2017.
Raviteja Vemulapalli, Felipe Arrate, and Rama Chellappa. Human action recognition by representing 3d skeletons as points in a lie group. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 588-595, 2014a.
Ravileja Vemulapalli, Felipe Arrate, and Rama Chellappa. Human action recognition by representing 3d skeletons as points in a lie group. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 588-595, 2014b.
Jiang Wang, Zicheng Liu, Ying Wu, and Junsong Yuan. Mining actionlet ensemble for action recognition with depth cameras. In 2012 IEEE Conference Computer Vision and Pattern Recognition, pp. 1290 1297. IEEE, 2012.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. 1EEE Transactions on Neural Net- works and Learning Systems, 2020.
12

---

Published as a conference paper at ICLR 2021
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How powerful are graph neural nelworks? ICLR, 2019.
Sijie Yan, Yuanjun Xiong, and Dahua Lin. Spatial temporal graph convolutional networks for skeleton-bane based action recognition. In Thirty-second AAAI conference on artificial intelligence, 2018.
Jiani Zhang, Xingjan Shi, Junyuan Xie, Hao Ma, Irwin King, and Din Yeung, Gaan: Gated attention networks for learning on large and spatiotemporal graphs. arXie preprint arXiv:1803. 07244, 2018.
Dongmian Zou and Gilad Lerman. Graph convolutional neural networks via scattering. Applied and Computational Harmonic Analysis, 49(3):1046 1074, 2020.
APPENDIX
A PROOFS
A.1 DETAILS AND PROOFS SEC. 2.3
To facilitate comparison with literature, we provide a summary of various graph convolution models in matrix notation, the precise definition of which will be detailed in below. For simplicity, only the linear transform part is shown, and the addition of bias and point-wise non-linearity are omitted.
Notation as in Section 2.1 suppose X E B"xO' is the input node feature, and Y e R the output feature,
L3Net (ours): = Σk= B&X where B& E Raxn is the local basis filter, and Aş E CC'x are the coefficients, both By and A are learnable.
ChebNet/Ger /GNN: Y Σl X where Ti(-)'s are Chebshev polynomials, Ż is the rescaled and re-centered graph Laplacian, Ti(L) E gnx*, and O E CCCx are trainable.
GAT: Y E X(0, where A R is the graph attention affinity computed adaptively from input features, and θ, E RCCx xCC are trainable and weight- shared with the parameters in A see more in below.
EdgeNet: = Σ/=1 P,XO, where P. = ITk_ = filters px. and O, E C''xC are trainable.
dy for sequence of trainable local
From the matrix formulation, it can be seen that when B₁ are the classical graph filtering operators, c.g. polynomials of L, and Ag the trainable θş, L3Net recovers the above graph convolution models in literature (c.f. Proposition 1]. In below we give more details, as well as the reduction to fitee-decomposed CNN (c.f. Proposition 2
A.1.1 LOCALLY CONNECTED GNN
Specifically, the construction in Coates & Ng 2011 Bruna et al. (0013) assumes that and u' belongs to the graph of different scales, coarse-grained layer produced by clustering of indices of the graph of the input layer. one generalize the construction to allow over-lapping of the receptive fields, and assume no pooling or coarso-graining of the graph, then the non-zero parameters are of the number
the fine graph, and u
Σ Nal CC' np CC',
where = IV, p is the average patch size Nul, and C' and C' are the number of input and output feature channels.
13

---

Published as a conference paper at ICLR 2021
A.1.2 CHEBNET/GCN, GAT AND EDGENET
ChebNet/GCN
In view of 1 ChobNet (Defferrard et al. 2016 makes use of the graph adjaceney matrix to construct M. Specifically, Axym := 1/2 AD-1/2 the symmetrized graph adjacency matrix (possibly including self-edge, then A equals original A plus I), and Lagm == I Asym has spectral decomposition Leym VAV" Let L ai + ag be the rescaled and re-centered graph Laplacian such that the eigenvalues are between [-1, 1], a1, 02 fixed constants. Then, written in n-by-n matrix form,
Mesc (m() o)(d ER,
where Ti()) is Chebshev polynomial of degree 1. As Asym and then L. are given by the graph, only 0t's are trainable, thus the number of parameters are
L CC
GCN (Kipf & Welling 2016 is a special case of ChebNet. Take L in and tie the choice of to and 01.
Me, ((c', (a) AgAsym) =: O(', a a/2 fixed constants,
where ((c,c) c) is trainable. This factorized form leads to the linear part of the layer-wise wise mapping Y AXO written in matrix form, where Á is n-by-n matrix defined as above, X (Y) is by-CC' (-C) array, θ is C'-by-C matrix. The model complexity is CC" which are the parameters in O.
GAT
In GAT (Vličković et al. 2017) R being the number of attention heads, the graph convo- lution operator GNN layer be written (omitting bias and non-linear mapping)
Y= Σ 1 XO,,
A
(r) ae = ((( w((
(6)
EveNg
where (W(r)a are the trainable parametrization of attention graph affinity mechanism A(r), which constructs non-negative affinities between graph nodes and adaptively from the input graph node feature X. In particular, Arr) shares sparsity pattern as the graph topology, that is, ( u/) # 0 only when u' E N:!")
In the original GAT, θ, = cir) where C(r'ss are fixed matrices such that the output from r-th head is concalenated into the output Y across r = 1,... R. Variants of GAT adopt channel mixing across heads, e-g. a generalization of GAT in Tsufi al. (2020)
extra trainable O, in (6) independent from ((K), Tsufi et al. (2020) also proposed higher- order GAT by considering powers of the affinity matrix A as well as the adge-varyyng version (c.f. Eqn. (39) in [sufi et al. (2020)). As this higher-order GAT and the edge-varying counterpart are special cases of the edgy-varying GNN, we cover this case in Proposition [ 3).
The model complexity of GAT: In the original GAT where θ, is tied with W(r), the number of parameters in one layer is R(C,C" + 20o), where Rt is the number of attention heads,
C' = CoR, and W(r), CC + RCo When O, are free from (W(r), ((()) in (6), the number of parameters is R(CC" + C,C + 2Co) & R(2CC' + 2C), where W(r) maps to dimension Co and θ maps dimension C.
EdgeNet (Edge-varying GCN)
Per Equ. (8) in Isufi et al. (2020). the edge-varying GNN layer mapping can be written
as
y
Φ
xe,,
(7)
r=0
k==
14

---

Published as a conference paper at ICLR 2021
where Po is an n-by-n diagonal matrix, and Qn. k 1,... ,7, are supported on No of each node u. The trainable parameters are {$x) and (0,), O : RC. Edge- varying GAT implements polynomials of averaging filters, and general edge-varying GNN takes product of arbitrary 1-order filters. The proof shows that EdgeNet layer is a special case of L3Net layer, while restricting Bş to be of the product form 99 rather than freely supported on (=(d)) for user-specified order (d1,"..,d)) ) is non-trivial restriction.
The trainable parameters: Or has LCC" many, 2o has n, and 4x h 1, L 1 each has mp(") many, p()) being the average size 1-neighborhood of nodes. Thus the total number of parameters is
LCC +n+ (L 1))p()) ~ L(CC" + mp
Proof of Proposition 4 Part (1): Since GCN is a special case of ChebNet, suffices to prove that (5) can be expressed in the form L3Net (2) for some K. By definition of L, mathenatically equivalently,
Mes0 = Σ [(C
Σ [olc Aaym)) = Σ Bild, A)
where the coelficients 3i's are determined by 0j's, per (c',c). Since A propagates to the I-th order neighborhood of any node, setting Bu(u', u) Abym u), Bu(u', u) is non-zero
when u' N 1 k K = L,, and then setting as (x,c c) Bx-1(d', gives in the
form of 22
Part (2): We consider as the GAT model. Recall that O, : RO¹ - R then 6 can be
re-written in the form of by letting
B M(u, u: d, = Σ (r) (u',
which is a special case of 12 where R K, A = Ba and O₂ = au. Since A w')
as function of u' is supported on u' E N
6 belongs to the L3Net model
2 where
dj =... dx= 1, in addition that Bg must be of the attention affinity form, l.e. built
from the altention coefficients Cur computed from input. X via parameters (W(r), (r1).
Part (3): Comparing with [ 1 have that
7 is special case of L3Net by letting
K L.
k
BN
k'=0
4g = Ok-1, and da = k for k- 1,... K.
A.1.3 STANDARD AND GEOMETRICAL CNN'S
Standard CNN on Rd, e.g. d = for audio signal and d = 2 for image data, applies discretized convolution to the input data in each convolutional layer, which can be written as (omitting bias which is added per c, and the non-lincar activation)
y(u, = Σ Σ we,c(ul u)x(u',dd) dElO'IEE
(10)
where U is grid Rd. We write in the way of "anti-comvoluttion" which has "u' w² rather than "u u"", but the definition equivalent. For audio and image data, usually regular mesh with evenly sampled grid points, and proper boundary conditions are applied when computing y(u.e) e) a boundary grid point u. E.g., boundary can be handled by standard padding as in CNN. As the convolutional filters we's are compactly supported, the summation of u' is on neighborhood of u.
15

---

Published as a conference paper at ICLR 2021
More generally, CNN's non-Euclidean domains constructed when spatial points sampled on an irregular mesh R.d e.g., a 2D surface in R The generalization of (10) is by defining the "patch operator" (assc et al. 2015 which pushes template filter w on a regular mesh on IR", d being the intrinsic dimensionality of the sampling domain, to local charts. Specifically,
the irregular mesh in the ambient space that have coordinates for a mesh of 2D surface in 3D, d = 2, and w is a template convolutional filter on R², For any local cluster of 3D mesh points No around point u, the patch operator Pu provides (Pa (u'))(")) for u' E N₂ by certain interpolation scheme on the local chart. The operator P. is linear in w, and possibly trainable. As a result, in mesh-based geometrical CNN,
s(u c)
E ((d e'ElCy
(11)
and one see that in Euclidean space taking (Paw)(u)) w(u' - u) reduces standard CNN as in 100.
11 to the
In both [10 and 111 spatial low-rank decomposition of the filters we'e can be imposed (Qiu
el al. 2018 This introduces set of bases (bs)a over space that linearly span the filters
Wel.e- For standard CNN in Rd by basis filters Rd and for geometrical CNN, they are defined the reference domain in Rd same we'er where d is the intrinsic dimension.
Suppose we'e = Ek=1 Be, for coefficients Be.(elee) by linearity,
(1
becomes
s(u,c)
E C'E(C"
(12)
and similarly for 10). The trainable parameters in 12 are Bk.(el,e) and the basis filters by 's the former has KCC" parameters, and the latter has Ex Pk. where pk is the size of the support of be in Te.d Suppose the average size is then the number of parameters is Kp. This gives the total number of parameters
KCC" + Kp.
Proof of Proposition g Since standard CNN is special case of geometrical CNN 11 we only consider the latter. Assuming low-rank filter decomposition, the convolutional mapping is 12) Comparing to the GNN layer mapping defined in [ one sees that
K Σ
M(',,; uz ,l,
Br (Paba)(()
which equals 2 if setting Bx u) (v'b and (x(c,e) = (x,(c))))
A.1.4 STRONG REGULARIZATION LIMIT
Proof of Proposition 5 The constrained minimization of R defined in (3
separates for each
u, k, and the minimization of (k) is given by
min R
w (A) w, s.t. ||ll2 2 au, >
(13)
For each u, k, the local Dirichlet graph Laplacian ( has eigen-decomposition L (x) (R) (V)"")), where (v(*) ( ( = I, and the diagonal entries of (A)) are eigenvalues of ((k) which are all 0 and sorted in increasing order. By the variational property of
eigenvalues, the minimizer of w 13 is achieved when w (xx) (,,1,, i.c., the eigenvector
associated with the smallest eigenvalue of (A) By that. the local subgraph is connected, this smallest eigenvalue has single multiplicity, and the eigenvector the Perron-Frobenius
vector which does not change sign. The claim holds for arbitrary au,k > 0 since eigenvector is defined up to constant multiplication.
16

---

Published as a conference paper at ICLR 2021
A/3.3
2
AP3..)
0.2
7 G ring graph
ANS
B E Span(T, A .44 .49
Figure A.1: A ring graph with 8 nodes. Polynomials of graph adjacency matrix A (or Laplacian matrix) preserve symmetry mirroring around any node, e.g., node 3, and cannot express local filter B
A.2 PROOFS SEC.
Proof of Proposition 4 Part 1): Let the graph be the ring graph with n nodes, and each node has 2 neighbors, n=8 shown in Fig. 1 (right). We index the nodes u = 0, O..... n-1 and allows oddition//uubrracteonn 1 when u' = and -1 when u' = -u++ -.+1. We show that B + f(A) for any f, and in contrast, sctting this B as the basis in (2) expresses the filter with =1
of u-v (mod n). Let be the "difference" filter B(u', u)
To prove that B + [(A) for any J, let Ta be the permutation of the n nodes such that Tu + u) (u v) for all v, i.e., mirror flip the ring around the node u. By construction, the graph topology of the ring graph is preserved under Tus that is, Ar., whether A the 0/1 value adjacency matrix or the symmetrically normalized one Asym = AD1/2AD-1/2 1/2 (D is constant on diagonal) or other normalized version as long as the relation A.. = A holds. By Lemma A.1 1), for any ʃ : + IR,
TTA A,
[(A)T, = [(A,,) TT = ((A)
this means that if B = f(4) for some f, then BTT nu B, which contradicts with the construction of B.
Part 2): Consider the two distributions of graph signals on the ring graph in 1), which we call "upwind/ /downwind" signals: Xup consists of finite superpositions of functions on the ring graph which are periodic, smoothil increasing from 0 to and then dropping to zero. Signals in Xup are under certain distribution, and Xdowm consists of the signals that can be produced by mirror-fiipping the upwind signals. That is, denoting Zup (Idown) an upwind (downwind) signal, Ta the permutation as in 1) around any node then
dist.
Tup
Edmons
where dist.
means equaling in distribution. Example signals of the two classes as illustrated
in Fig.
Same as in 1), by construction Ar,, = A. Let ((L) be the mapping to the L-th layer spectral GNN feature, for Tup an upwind signal, Lemma A.1 2) gives that
FOL) [ATTaaa = p(2)) [A Ta = n. F (L) [A] [A]xup-
The last layer applies group invariant operator U, then
U UP(D) (() [A] U (b) [A]
this gives that
U U dist. [A]TTap = UF [A]xup:
which means that the final output deep feature via [ are statistically the same for the input signals from the two classes.
Meanwhile, the difference local filter in the proof of 1) can extract feature to differentiale the two classes: with Relu activation function, the output feature after one convolutional layer and a global pooling, which permutation invariant, can be made strictly positive for one class, and zero for the other class. Thus, L3Net with 1 layer and 1 basis suffices to distinguish the X up and X Xdown signals.
n
17

---

Published as a conference paper at ICLR 2021
Lemma A.1 (Permutation equivariance, Proposition 1 in Gama et al. 2019a Let A be the (possibly normalized) graph udjacency matrix, for any iripul signal I - R, and E Sn a permutation of graph nodes,
1) The spectral graph convolution mapping ((A) salisfies that
f(A,)== = =xfx=x x{(),, Ag == An"
2) Let [A] be the mapping to the 1-th layer spectral GNN feature with graph adjacency A, then
F [Ar]TT xF
Proof of Lemma A.1, Proved in Gama et al. (2019a) and we reproduce with our notation for completeness.
Part 1): Denote the n-by-n permutation matrix also by T, then by definition, f(A) US(AJUT where A UAUT is the diagonalization and U is orthogonal matrix, thus
( x²) = =UJ(A)U* x² = x({))
and this proves 1).
Part 2): Each spectral GNN layer mapping adds the bias and the node-wise non-linear acti- vation mapping to the graph convolution linear operator, which preserves the permutation equivariance. Recursively applying to layers proves 2).
A.3 PROOFS IN SEC. 3.2
Proof of Theorem 1 By definition,
K (u) = ak (Bx (.)) x(d + bias),
k=1
then since a is non-expansive, Vu V,
K
1/2
(AY(W) <
NOo S ||all2
Σ
(Ba(, maae
(14)
A=1
By that
(BB( u), AX(()) wooo [| u]]l 2.1 (1 2,N5"
(15)
have that
AA S ||112 Σ
(Ba(, Axx()) x
BEV
< ||al12
|Ba 2
| 2,
< (111)128(1)3
Σ
1AXO)2 2
(16)
u.k
and observe that
K =
K
Σ 12
ΣΣ Σ (AX(O) = Σ Σ
((EEN()s) |AX(U)2
kmm NEV vEN((d))
Rm U.VVV
K
K
ΣΣ 1 (MEN("N) (x(0))2
ΣΣ [ (IX())
E Kp Σ (x)))
k=lrEV
DEV
where used the assumption on Kp to obtain the last S. Then 16
continues
which proves that | /K) claimed.
18

---

Published as a conference paper at ICLR 2021
Same in the proof of Theorem decomposition L. w Ald (u("))" has that (w y = L, and, under the connectiv-
Proof of Theorem
have
14
The eigen-
(k)
ity condition of the subgraph, the diagonal entries of Au (u, Mi = ((A (12
(k) all O. Thus
which gives the Cauchy-Schin Schwarz with weighted 2-norm as [Be(:, u), AX(() w & [ ") (IX())
(17)
Then similarly as in 16] using the definition of ((2) and the the condition with p. we obtain that
Σ (1) & (1aall3(2)3
Σ (-)
2,N1
(18)
WEV
u.k
and the rest of the proof is the same, which gives that
Σ
AY (u))
WEV
which proves the claim.
B UP/DOWN-WIND CLASSIFICATION EXPERIMENT
B.1 DATASET SETUP
We generate the Up/Don Down wind dataset on both ring graph and chain graph with 64 nodes. Every node is assigned to probability drawn from (0.1) uniform distribution. Node with probability less than lhreshold = 0.1 will be assigned with a gaussian distribution with std = 1.5. Each gaussian distribution added is masked half side. Distribution masked left half is the 'Down Wind' class, distribution masked right half the 'Up Wind' class, as shown in left plot in Fig. 3. We then sum up all half distributions from different locations in each sample. We generate 5000 training samples and 5000 testing samples.
B.2 MODEL ARCHITECTURE AND TRAINING DETAILS
Network architectures.
2-gen-layer model:
1-gen-layer model:
where GraphConv can be ChebNet or L3Net.
Training details.
We choose the Adam Optimizer, batch size of 100, set initial learning rate of 1 xx100 10-3, make decay by 0.1 80 epoch and train for 100 epochs.
B.3 ADDITIONAL RESULTS
We report additional results using 1-gen layer architecture in Tab. A.1 shows stronger classification performance than ChebNet.
Our L3Net again
C EXPERIMENTAL DETAILS
C.1 CLASSIFICATION OF SPHERE MESH DATA
Spherical mesh We conduct this experiment on icosahedral spherical mesh (Baumgardner
& Frederickson 1985). Like S2CNN (Cohen al. 2018), we project digit image onto surlace
19

---

Published as a conference paper at ICLR 2021
Table A.1: results of 1-gen layer models
Gnn model
order
paraass
ring graph Aec
chain graph Age
L=3
0.2k
50.80 0.22
50.60 0.21
ChebNet
L=5
0.3k
51.14 + 0.21
51.07 = 0.35
L=9
0.4k
51.68 0.38
50.96 0.29
L=30
1.1k
51.37 + 0.14
50.70 0.16
99.96
L3Net
0;1:2
0.8k
99.96
0.01
99.92 0.01
of unit sphere, and follow Jiang et al. (2019) by moving projected digit. to equalor, avoiding coordinate singularity at poles.
Here, details the subdivision scheme of the icosahedral spherical mesh we used. Start with an unit icosahedron, this sphere discretization progressively subdivide each face into four equal triangles, which makes this discretization uniform and accurate. Plus, this scheme provides a natural downsampling strategy for networks, as it denotes the path for aggregat- ing information from higher-level neighbor nodes to lower-level center node. We adopt the following naming convention for different mesh resolution: start with level-0(LO) mesh(i.e., unit icosahedron), each level above is associated with a subdivision. For level-i(L;), prop- ertics of spherical mesh are:
Ne 30 1,, 20 4+i, No Ny +
(19)
in which N,, Ne, N2 denote number of edges, faces, and vertices.
To give direct illustration of how many nodes each level of mesh has, we list them below,
LO 12 nodes
L1 42 nodes
L2 162 nodes
L3 642 nodes
L4 2562 nodes
L5 10242 nodes
Network architectures We use three-stage GNN model for this Sphere with each stage conduct convolution on spherical mesh a specific level. Detailed architecture (suppose mesh levels used are Li, Lj. Lk):
Cow.::/DDD...AAA....Dooamaa/reed ResBlock AAAB:oo(((L.L..ssssss-////AOOOO
We use the 4-stage model architecture for SphareMoodeNett400, where 4 mesh levels are: L5, L4, L3, L2. Detailed architecture are:
Rrct (-r FC((0),
where the GraphConv(feat in, feat out) in above model architectures can be either Mesh Convolution layer Graph Convolution layer, and "ResBlock" is bottleneck module with two x convolution layers and one GraphCony layer.
Training Details For MpIe experiments, we use batch size of 64, Adam optimizer, initial learning rate of 0.01 which decays by 0.5 every epochs. We totally train model for 100 epochs.
For SphereMoodeINet400 experiment, we batch size of 16, Adam optimizer, initial learning rate 0.005 which decay by 0.7 every 25 epochs. We totally train 300 epochs.
Results fine mesh
Tab. A.2 show the results of SphereMNIST and MpderetModelNet.0 on fine meshes on the sphere. Specifically, the mesh used for SphereMNIST here is of levels L4, L2, and the SphereMoodeINet-000 mesh of levels L5, L4, L3, L22 same in Jiang et al. 2019)
20

---

Published as a conference paper at ICLR 2021
Table A.2: Results on SphereMNIST and SphereMModelNet-ii following sctup in Fang et al.
2019
SphereMNNSST
SphereModdelNet40)
Model
Acc
Acc
S2CNN
Cohen et al
2018
96.0
85.0
UGSCNN
Jhang
99.2
90.50
GCN
95.8
87.07
ChebNet(Z=4) ChebNet(L=5)
88. 30
ChebNet(L=66
ChebNet
88.78
L3Net (1123)
L3Net (112)
98.90
89.67
C.2 FACIAL EXPRESSION RECOGNITION
Landmarks setting 15 landmarks are selected from the standard 68 facial landmarks defined in AAM (Cootes et al., 2001], and edges are connected according to prior information of human face, c.g., nearby landmarks the eye are connected, see Fig. 1 (left).
Dataset setup
CK+:
The CK+ dataset (Lucey el al. 2010) is the mostly used laboralory-contrrllee FER dataset contains 327 video sequences from 118 subjects with seven basic expression labels (anger, contempt, disgust, fear, happi- ness, sadness, and surprise). Every sequence shows a shift from neutral face to the peak expression. Following the commonly used '(static) image-based' methods (Li & Deng 2020). we extract the one three frames in each expression sequence that have peak expression information in the CK+ dataset, and form a dataset with 981 image samples. Every facial image is aligned and resized to (120, 120) with face alignment model (Bulat & Tzimiropou- los 2017). and then we use this model again to get facial landmarks. As we describe Sec. 4.2, select 15 from 68 facial landmarks and build graph on them. The input feature for each node an image patch centered at the landmark with size (20, 20), concatenated with the landmark's coordinates, so the total input feature dimension is 402.
(downloaded from: http::// www. http://www...f.oo....o jeffcohn. wtw.eeefooooeeeeeeeooooooooooo net/resources//
FER13:
FER13 datasel. Goodfellow et al. 2013 a large-scaled, unconstrained
database collected antomatically by Goole Image API (downloaded from:
https:/ /www.. /tw.://wwwl..w....//////// com / challenges in wnw.repreentatiion-eeeree fawarminn---ccccccpp-e-eee -eciall-epresssion
dala). It contains 28,709 training images, 3589 validalion images and 3589 test images ot size (48, 48) with seven common expression labels as CK+. We align facial images, get facial landmarks, and select nodes build graph the same way as we do in CK+ Input features are local image patch centered at each landmark with size (8, (8.8) and landmark's coordinates, so the total input feature dimension 66.
arcognalaon-challlne
Network architectures.
CK+:
FER13:
ReLU-FC(7).
where GraphCony(feat in, feat.oout) here can be any type of graph convolution layer, in- cluding our L3Net.
Training details.
CK+:
We use 10-fold cross validation as Ding al. (2017). Batch size is set 16, learning rate is 0.001 which decay by 0.1 if validation loss remains same for last 15 epochs. We choose Adam optimizer and train 100 epochs for each fold validation.
21

---

Published as a conference paper at ICLR 2021
25
Figure A.2: Illustration of 25-poiut body joints and graph.
FER13:
We report results on test set. Batch size is set as 32, learning rate is 0.0001 which decay 0.1 validation loss remains same for last 20 epochs. We choose Adam optimizer and train models for 150 epochs.
Runtime analysis details. In section 4.2, report the rumning time of our L3Net 1,1,2,3), 13. 13.02ms, and best ChebNet, 12.56ms on CK+ dataset, which are comparable. Here, we provide more details about this. The time use to compare is the time of model finishing inference on validation set with batch size of 16. For each model, we record all validation time usages in all folds and report the average of them. The Runtime analysis is performed single NVIDIA TITAN V GPU.
C.3 SKELETON-BASED ACTION RECOGNITION
Dataset setup.
NTU-RGB+D:
NTU-RGB+D (Shahroudy al., 2016 large skeleton-based action recognition dataset with three-dimensions coordinates given to every body joint (downloaded from: http://rosee.. mrosee.ntu.e edu.sg/
rregueeeeeeerddeeee Adeuesteerdddd.e. asp DS-3). It comprises 60 action classes and total 56,000 action clips. Every clip is captured by three fixed Kineticsv2 sensors in lab environment performed by one of 40 different subjects. Three sensors are set at same height but different horizontal views, -45% 0 45% There are 25 joints tracked, as shown Fig. A.2 Two experiment setting are proposed by Shahroudy et al. (2016), cross-view (X-view) and cross-subject (X-sub). X-view consists of 37,920 clips for trainin and 18960 for testing, where training clips are from sensor on 0%, 0², 455,, testing clips from sensor on -45.. X-sub has 40,320 clips for training and 16,560 clips for testing, where training clips are from 20 subjects, testing clips are from the other 20 subjects. We test our model on both settings.
Kinetics:
Kinetics (Kay al., 2017 is large and most commonly-used action recog- nition dataset with nearly 300,000 clips for 400 classes (downloaded from: We follow Yan et al. (2018) to
https://dda http://deemddddcc// coweeoo/////eeeeeee /resea/reacc////ee bissarcch/open-sooe open-source wwsorre/kinnttsss/ /kinetis)....... get 18-point body joints from each frame using OpenPose (Cao et al. 2017] toolkit. Input features for cach joint to the Network is (x,, y. p), in which x, J are 2D coordinates of the joint. and p the confidence for localizing the joint. To climinate the effect of skeleton- based model's inability to recognize objects in clips, we mainly focus on action classes that requires only body movements. Thus, conduct proposed by Yan et al. (2018). This is a small dataset that contains 30 action classes strongly related to body motion. Note that there are severe data missing problem in landmark coordinates in Kinetics data, so we also use our regularization scherne this experiment.
experiments
Kinetics-Motion,
Network Architectures.
22

---

Published as a conference paper at ICLR 2021
NTU-RGB+D:
We follow the architecture in Yan et al. (2018
(1 STGraphConv (1 215.,266...)--SSAAAgooooo.o0
(64,,4,9.s1)-55 (444444A0.)))SSTTaaaaCCCoooo11
STGraphConv
Kinetics:
We also design a computation-efficies architecture for Kinetics-Motion with larger temporal downsampling rate, which results in less forward time:
STGraphConv 9.2 (.333.......2SSTtaaaCCnmnmma 2-) (et.:2))SSTTrraaaooooo444...... STGraphConv 69,96699ss11. (5566.991L/SSTrraaaCorrr....... 1et.112289988 9122)-STTGraphhConn(22222 128,5,)
SoGraphConv [28,,188,,, 110111555.ss--TGGaaacc//////// 222. 22t.:/.....2...11aaaaooo222222.. STGraphConv (256,256,3) (55 -SSTAvgPooo-((((0)
where the structure of STGraahCCon((eett. feat.out, ral_stride) is:
tempo-
GraphConv(feat.in
feat_out,
tempo-
sereel,elssize,, -N-
Training Details
NTU-RGB+D:
We use batch size of 32, initial learning rate of 0.001 which decay by 0.1 at (30, 80) epoch, and total train 120 epochs. SGD optimizer is selected. We padding every sample temporally with to 300 frames.
Kinetics:
We use batch size of 32, initial learning rate of 0.01 which decay by 0.1 at (40, 80) epoch, and total train 100 epochs. SGD optimizer is selected. We padding every sample temporally with 0 to 300 frames, and during training, we perform data augmentation by randomly choosing 150 contiguous frames.
C.4 DETAILS OF EXPERIMENT ON MNIST
C.4.1 SIMULATED GRAPH NOISE ON 7 7 MNIST.
Here we describe three types of noise in our experiments:
Gaussian noise. Given a X 7 image from MNIST, we sample 49 values from N(0, std?). The std controls the strength of noise added. We conduct experiments under std 0.1,0.2 0.3 as shown in Tab. 3 The amount noise also measured by PNSR which is standard for image data.
Missing value noise. Given a image, we randomly sample 49 values from U 1), and select nodes with probabilities less than a threshold. This threshold is called noise_level, which controls the percentage of nodes affected. Then, we remove the pixel value at those selected nodes. Experiments with noise_level = 0.1, 0.3 are conducted.
Graph node permutation noise. For each sample, center node which has exact neighbors. Then, we rotate its neighbors clockwise by de- gree, e.g., top neighbor becomes right neighbor, and then we update the indices of permuted nodes.
randomly select. a permuta atmmulation
23

---

Published as a conference paper at ICLR 2021
Table A.3: Results on MNIST with grid size 28 28, LaNet-pooling graph pooling between convolu- tional layers.
Table A.4: Results on MNIST with grid size 14
Model
basee order
in #perana
[w//n
Ace
Model
bases ordec
#paroma [w/o FC)
Acc
GON
7:4k
8.6k
04.00
0.00
Lm0
10.7k
96. 57
0.09
ChobNet
Lm5
14.58
96. 85
0.12
L--7
14.5k
96 98
0:19
07 83
0:18
0:112
1:1/2
reg0.001
LSNet
1:1/2/33
poolligg
Table A.5: Results on MNIST with grid size 7 x with different levels of missing value
Model
bases order
reg
#params (w/o FC)
Ace(original)
Acc(psnr 18.70)
Acc(penr 15.33)
Acc(psnr 13.15)
GON
2.4k
90.02 + 0.24
$3.44
0.13
77.23
+ 0.13
71.67 = 0.08
L=3
6.5k
92.85 1. 0.09
87.09
1 0.18
82.11 1 0.18
76.15 1: 0.26
L=4
0.28
ChebNet
L=5
10.7k
93.2 = 0.07
87.01 = 0.14
82.01 0
76.21 + 0.38
L=6
12.7k
L=7
14.8k
93.45 0.06
87.08 = 0.11
81.00 0.11
75.31 + 0.34
1:1:2
8.4k
93.56
81.14
LaNet
1:1:2
0.5
8.4k
93.85 1: 0.13
87.22 0.23
82.84
0.11
76.48 1 0.23
1;1:2;3
0.5
12.2k
93.85 0.15
87.22 1 0.08
82.64 1 0.31
76.08 1. 0.38
C.4.2 NETWORK ARCHITECTURE AND TRAINING DETAILS
We use the architecture for different experiment settings:
where GraphConv can be different types of graph convolution layers. We set batch size to 100, use Adam optimizer, and initial learning rate to le-3. Learning rate will drop by 10 if the least validation loss remains the same for the last 15 epochs. We set total training epochs 200. We use 10,000 images for training.
We also adopt graph pooling layers the above architecture:
GraphConv(1, BN--e Graph Pooling-FC(11).
64)-BN-ReLU-
More discussion about graph pooling layer and multi-scale graph convolution detailed in Appendix C.5
C.4.3 ADDITIONAL RESULTS
Here, we show experiments results on 28 28, 14 14 grid, as well as 7 x grid with missing values. Tab. A.3 shows results on 28 x 28 image grid. Our model have better performance than other methods.
Tab. A.4 shows results on 14 x 14 image grid, where our L3Net have comparable results with the best ChebNet (Defferrard et al. 2016 method.
We shows our results on 7 x 7 image grid with missing values in Tab. A.5 With regu- larization, L3Net achieves the best performance in every experiment with different noise levels.
C.5
MULTI-SCALE GRAPH CONVOLUTION
The proposed L3Net graph convolution model 2 is compatible with graph down/up- sampling schemes to achieve multi-scale feature extraction.
usually implemented as a separate layer between graph convolution layers. As an example, Fig. illussrats three levels of graphs produced from originally 14x 14 image grid, denoted G1, G2, G3,, and they have 176, 45 and nodes
The graph down/up-sampling
24

---

Published as a conference paper at ICLR 2021
Figure A.3: Three levels of graphs 14x14 image grid. From left to right: the level G3 (the coarsest) bottom level G1 (the finest). The red square (pink circle) indicates node on G3 (G2) and its local neighborhood on G2 (G1), which the graph pooling is applied.
respectively. On G1, 10% of pixels which contain the lowest amount of pixel intensitics over the dataset are removed, and those nodes are located near the boundary of the canvas. For each node xy in the coarse-grained graph G2, neighborhood consisting of nodes in G1 is constructed, called N(x;; G1). A pooling operator computes the feature x' from those on [x G1), and the pooled feature used as the input to the graph convolution on G2. A similar graph pooling layer is used from G2 to G3. The graph lopology and local neighborhoods are determined by grid point locations. Using a two-layer convolution with graph poolings in between from G1 to G3, and the other setting same as in Table A.4 L3Net obtains 97.33 + 0.15 test accuracy (basis order 1; 1;2, with regularization 0.001).
We have also applied graph pooling lavers on regular image grid on the 28x28 MNIST dataset. The results, reported in Table A.3] show that multi-scale convolution in L3Net not only improves the classification accuracy but also reduces the number of parameters.
Graph up-sampling layer can be used similarly. These multi-scale approaches generally apply to graph convolution models, sec, c.g., the hicrarchical construction originally proposed for locally-connected GNN (Coates & Ng 2011 Bruna et al. 2013). There is also flexibility in defining the graph down/ up-sampling schemes, and the choice depends application. An example of graph sampling operator on face mesh data is given in (Ranjan et al. 2018). At last, apart from using separate down/up /up-samliing layers, it is also possible to extend the 2 to directly implement graph down/ up-sampling which would be similar to
L3Net model the convolution-wilb-stiee
(conv-t) operator in standard CNN. Specifically, between G1 and G1+1, the local basis filter (u, u/) is defined for u' E Gi and G1+1, and Bx x') # only when w' is local neighborhood of u. matrix notation, Bg is of size [G441--by-IGi and is sparse according to the graph local neighborhood relation between G and G4+1.
25


Reviews:
[{"review_id": "_1NXB6vEDBH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "####################\nPros:\n$\\bullet$ The proposed graph convolution method is tested on different problems (object recognition on the spherical mesh, facial expression recognition, action recognition on the face and body landmarks), and real-world datasets.\n\n$\\bullet$ The proposed method performs well both under the missing node and feature and graph noise. Particularly the effect of local graph Laplacian regularization is notable. \n\n$\\bullet$ The relationship between the proposed L3Net and previous spatial and spectral graph convolutions is theoretically explained.\n\n$\\bullet$ The complexity of the L3Net is significantly lower than locally connected GNN, and it is more suitable for small-size graphs such as the face or body keypoints.\n\n####################\nCons:\n$\\bullet$ In face experiments, pixel values around each node were taken as node features, however, in a similar setting in action recognition, they were not used. Considering the temporal data as in CK+, applying a similar setting by changing ST-GCN blocks with L3Net would make it comparable. \n\n####################\nMinor:\n$-$ In many parts, typo error in MNIST dataset's name (\"MNSIT\") .\n$-$ 2.3 first paragraph, graph \"convolutoins\"-> convolutions.\n$-$ 1.1. second paragraph: \"Chebyshev polynomial in Chenbet\"-> \"ChebNet or ChebConv\"\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "NvFA2KAtjj", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "SUMMARY:\n\nThe paper presents a graph neural network (GNN) architecture with learnable low-rank filters that unifies various recently-proposed GNN-based methods. The local filters substitute the graph shift operator (GSO) by a learnable set of parameters that capture the local connectivity of each node in the graph. Moreover, a regularization penalty is proposed to increase the robustness of the model and prevent these local structures to overfit. The paper provides proofs to justify the generality of the approach and how different methods can be seen as a particularization of the proposed scheme. Two theorems are also proved to claim the stability of the GNN architecture against dilation perturbations in the input signal. Several numerical experiments are conducted to empirically test the usefulness of the model.\n\n\nSTRONG POINTS:\n\nThe paper introduces a new GNN-based approach with larger discriminability power.\n\nThe proposed approach generalizes various previously existent architectures. This is proved in the appendices.\n\nA regularization technique is proposed to avoid overfitting to local particularities of the data.\n\nTwo theorems are introduced to proof the stability of the network against dilation in the input signal.\n \nThe numerical experiments are extensive and convincing. This is one of the strongest points of the paper.\n\nThe paper is well-structured and the style is appropriate. It is easy-to-follow and the points are clearly stated.\n\n\nWEAK POINTS:\n\nReplacing the GSO with a set of learnable parameters increases the discriminability power of the network, at the cost of sacrificing various properties of common GNN architectures. For example, this technique is no longer permutation equivariant, and transferability to larger networks will no longer be an option, as long as the learnt parameters are graph-dependant.\n\nScalability problems appear when the network grows in size. This, and some possible ways of tackling it, are discussed in the conclusion.\n\nAlthough the theorems offer insights on the robustness of the network against perturbations on the input signal, they are restricted to dilation perturbations (which are proportional to the input signal). This is not commonly the case, perturbations often follow distributions that has nothing to do with the input signals. \n\n\nOVERALL ASSESMENT AND RECOMMENDATION:\n\nThe paper introduces a new architecture with larger discriminative power that generalizes various state-of-the-art methods. Although the theoretical results are not particularly strong, they are undoubtedly insightful. Then, the empirical performance of this technique is exhaustively validated through several experiments. Thus, in my opinion, this paper should be accepted.\n\n\nRECOMMENDATIONS TO THE AUTHORS:\n\nUsing matrix notation would be helpful to clarify various equations and capture the attention of a broader range of researchers. Equally important, it will also contribute to establish links between the schemes proposed in the paper and well-established techniques in the field of graph signal processing (GSP).\n\nDescribing the connection between the operator $B_k$ and classical graph operators (adjacency, Laplacian, normalized Laplacian...) would be clarifying. Consider adding a couple of lines pointing out this relation. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "6vmg7-nmlEh", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors present a new definition of graph convolution that is also shown to generalize well-known existing ones.\n\nPros:\n- interesting new definition of graph convolution\n- good theoretical contribution \n\nCons:\n- experiments could have used more widely adopted benchmarks\n\nThe novel contribution of the paper is sound and the theoretical explanation allows to understand the connections with existing graph convolution definitions. \n\nThe experiments are well conducted and I appreciate the indication of the standard deviation in the results. They also show significant gains with respect to the other techniques. While the currently reported experiments are adequate, it would have been more interesting to test the method on emerging benchmarking frameworks such as [1] to get better insights on the perfromance on a standardized setting.\n\n[1] Benchmarking Graph Neural Networks, \nVijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, Xavier Bresson, https://arxiv.org/abs/2003.00982", "extra_scores": {}, "extra_text": {}}, {"review_id": "2a9u2cCyvo", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed L3Net which is a new graph convolution with decomposing the learnable local filters into low-rank. It can contain both spatial and spectral graph convolution (including ChebNet, GAT, EdgeNet and so on) as subsets. It is also robust to graph noise. Experiments are conducted on mesh data, facial recognition and action recognition, indicating out-performed performance over baselines. Its robustness to graph noise is also tested.\n\nIn general, the motivation, novelty and validation are good. However, I have the following concerns:\n\nAlthough the authors demonstrate and explain the advantage and disadvantages of L3Net, the authors do not explain the applicability of down-sampling and up-sampling in L3Net. For example, following max-pooling and up-sampling in DCNN, ChebNet can be integrated into mufti-scales for enhancing the performance (see https://arxiv.org/pdf/1807.10267.pdf ), how about formulating L3Net into multi-scales?\nIn the experiments, I saw that three convolutional layers are used in Section 4.1 (4.2, 4.3 and 4.4 seems do not offer the depth information of L3Net). I feel that three is a really shallow network. Why deeper networks are not used? Can the authors kindly comment/validate on this please?\nIn Proposition 1, it seems that a control of “K” and “L” can offer different options between ChebNet, GAT and EdgeNet. In practical training, are these settings of “K” and “L” easy to train/converge, with always good performance and computationally light? Are validation offered to prove this proposition and to compare the different options offered by L3Net to ChebNet, GAT and EdgeNet? If not, can the authors give reasonable comments on this please?\nIt seems the regularization in Section 2.2 is a very important contribution of this paper, however, no ablation study is offered (comparison between with or without regularization). Can the authors kindly validate this please?\nIn Figure 1, the definition of variable \\mu, c, k, M and K are not defined which makes the figure less easy to understand. Could the authors kindly add these on please?\nIn Figure 1, the authors use “left” and “right” to distinguish the four figures, this is kind of confusing. Could the authors use a, b, c and d for the figure label please? The same for Figure 2 where the authors use “plots” and “table” to distinguish different subplots. I think this can also be improved in similar way. Also other figures.\nIn Section 2.1, |V|=n. I feel that “N” would be more appropriate here, as it represents the number of nodes.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers expressed consistent enthusiasm on this submission during the review process. No reviewers expressed concerns and objections to accept this submission during discussion. It is quite clear this is a strong submission and deserves accept.
Decision: Accept (Spotlight)