{"id":805,"date":"2022-09-15T13:40:53","date_gmt":"2022-09-15T13:40:53","guid":{"rendered":"http:\/\/summergeometry.org\/sgi2022\/?p=805"},"modified":"2022-09-15T13:40:53","modified_gmt":"2022-09-15T13:40:53","slug":"exploring-frame-averaging-for-invariant-and-equivariant-network-design","status":"publish","type":"post","link":"https:\/\/summergeometry.org\/sgi2022\/exploring-frame-averaging-for-invariant-and-equivariant-network-design\/","title":{"rendered":"Exploring Frame Averaging for Invariant and Equivariant Network Design"},"content":{"rendered":"\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<p class=\"has-text-align-center wp-block-paragraph\"><em>written by Nursena Koprucu and Ruyu Yan<\/em><\/p>\n\n\n\n<h6 class=\"wp-block-heading\">Introduction<\/h6>\n\n\n\n<p class=\"wp-block-paragraph\">In the first week of project SE(3) Invariant and Equivariant Neural Network for Geometry Processing, we studied the research approach <strong>frame averaging<\/strong> that tackles the challenge of representing intrinsic shape properties with neural networks. Here we introduce the paper <em>Frame Averaging for Invariant and Equivariant Network Design<\/em>[1] which grounded the theoretical analysis of generalizing frame averaging with different data types and symmetry groups.<\/p>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">Motivation<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Deep neural networks are useful for approximating unknown functions with combinations of linear and non-linear units. Its application, especially in geometry processing, involves learning functions invariant or equivariant to certain symmetries of the input data. Formally, for a function \\(f\\) to be <\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><em>invariant<\/em> to transformation \\(A\\), we have \\(f(Ax)=f(x)\\);<\/li><li><em>equivariant<\/em> to transformation \\(A\\), we have \\(f(Ax)=Af(x)\\).<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">This paper introduced Frame Averaging (FA), a systematic framework for incorporating invariance or equivariance into existing architecture. It was derived from the observation in group theory that<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>Arbitrary functions \\(\\phi:V\\rightarrow\\mathbb{R}, \\Phi:V\\rightarrow W\\), where \\(V, W\\) are some vector spaces, can be made invariant or equivariant by <em>symmetrization<\/em>, that is averaging over the group.<\/p><\/blockquote>\n\n\n\n<p class=\"wp-block-paragraph\">Instead of averaging over the entire group \\(G\\) with potentially large cardinality, where exact averaging is intractable, the paper proposed an alternative of averaging over a carefully selected subset \\(\\mathcal{F}(X)\\subset G\\) such that the cardinality \\(|\\mathcal{F}(X)|\\) is small. Computing the average over \\(\\mathcal{F}(X)\\) can efficiently retain both the expressive power and the exact invariance\/equivariance.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Frame Averaging<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Let \\(\\phi\\) and \\(\\Phi\\) be arbitrary functions, <em>e.g.<\/em> neural networks.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Let \\({G}\\) be a group with representation \\({p_i}\\)\u2019s that preserves the group structure by satisfying \\({p_i}(gh)= {p_i}(g){p_i}(h)\\) for all \\({g}, {h}\\) in \\({G}\\).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">We want to make<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>\\(\\phi\\) into an invariant function, <em>i.e.<\/em> \\(\\phi(p_1(g){X})= \\phi({X})\\); and<\/li><li>\\(\\Phi\\) into an equivariant function, <em>i.e.<\/em> \\(\\Phi(p_1(g){X})= {p_2(g)}\\Phi({X})\\).<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Instead of averaging over the entire group each time, we will do that by averaging over group elements. Specifically, we will take the average on a subset of the group elements &#8211; called a <em>frame<\/em>.<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>A <em>frame<\/em> is defined as a set valued function \\(\\mathcal{F}:V\\rightarrow\\ {2^G \\setminus\\emptyset}\\).<\/p><\/blockquote>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>A frame is \\(G\\)-equivariant if \\(F(\\rho_1(g)X) = gF(X)\\) for every \\(X \\in V\\) and \\(g \\in G\\) where\\(gF(X)= \\{gh|h \\in F(X)\\}\\) and the equality means that the two sets are equal.<\/p><\/blockquote>\n\n\n\n<h3 class=\"wp-block-heading\">Why are the equivariant frames useful?<\/h3>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"946\" height=\"452\" src=\"http:\/\/summergeometry.org\/sgi2022\/wp-content\/uploads\/2022\/08\/Screen-Shot-2022-08-03-at-16.55.40.png\" alt=\"\" class=\"wp-image-968\" srcset=\"https:\/\/summergeometry.org\/sgi2022\/wp-content\/uploads\/2022\/08\/Screen-Shot-2022-08-03-at-16.55.40.png 946w, https:\/\/summergeometry.org\/sgi2022\/wp-content\/uploads\/2022\/08\/Screen-Shot-2022-08-03-at-16.55.40-300x143.png 300w, https:\/\/summergeometry.org\/sgi2022\/wp-content\/uploads\/2022\/08\/Screen-Shot-2022-08-03-at-16.55.40-768x367.png 768w\" sizes=\"auto, (max-width: 946px) 100vw, 946px\" \/><figcaption>Figure 1: Frame equivariance (sphere shape represents the group \\(G\\); square represents \\(V\\)).<\/figcaption><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">If we have a case where the equivariant frame is easy to compute, and its cardinality is not too large, then averaging over the frame, provides the required function symmetrization. (for invariance and equivariance).<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p><strong>Frame Averaging<\/strong><\/p><p>Let \\(\\mathcal{F}\\) be a \\({G}\\) equivariant frame, and \\(\\phi:V\\rightarrow\\mathbb{R}, \\Phi:V\\rightarrow W\\) be some functions.<\/p><p>Then, \\(\\langle \\phi \\rangle _F\\) is \\(G\\) invariant, while \\(\\langle \\Phi \\rangle _F\\) is \\(G\\) equivariant.<\/p><\/blockquote>\n\n\n\n<h3 class=\"wp-block-heading\">Incorporating G as a second symmetry<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Here, we have \\(\\phi, \\Phi\\) that is already invariant\/equivariant w.r.t. some symmetry group \\(H\\). We want to make it invariant\/equivariant to \\(H \u00d7 G\\).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Frame Average second symmetry<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Let \\(\\mathcal{F}\\) be a \\({G}\\) equivariant frame, and \\(\\phi:V\\rightarrow\\mathbb{R}, \\Phi:V\\rightarrow W\\) be some functions.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Then, \\(\\langle \\phi \\rangle _F\\) is \\(G\\) invariant, while \\(\\langle \\Phi \\rangle _F\\) is \\(G\\) equivariant.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Assume \\(F\\) is \\(H\\)-invariant and \\(G\\)-equivariant. Then,<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>If \\(\\phi:V\\rightarrow\\mathbb{R}\\) is \\(H\\) invariant, and \\(\u03c1_1,\u03c4_1\\) commute, then \\(\\langle \\phi \\rangle _F\\) is \\(G\u00d7H\\) invariant.<\/li><li>If \\(\\Phi:V\\rightarrow W\\) is \\(H\\) equivariant and \\(\u03c1_i, \u03c4_i, i = {1,2}\\), commute then \\(\\langle \\Phi \\rangle _F\\) is \\(G\u00d7H\\) equivariant.<\/li><\/ul>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Efficient calculation of invariant frame averaging<\/strong><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">We can come up with a more efficient form of FA in the invariant case.<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>The <em>stabilizer<\/em> of an element \\(X\u2208V\\) is a subgroup of \\(G\\) defined by \\(G_X =\\{g\u2208G\u2223\u03c1_1(g)X=X\\}.\\) \\(G_X\\) naturally induces an equivalence relation \u223c on \\(F(X)\\), with \\(g \u223c h \u21d0\u21d2 hg^{\u22121} \u2208 G_X.\\) The equivalence classes (orbits) are \\([g] = {h \u2208 F(X)\u2223g \u223c h} = G_Xg \u2282 F(X), for g\u2208F(X)\\), and the quotient set is denoted \\(F(X)\/G_X.\\)<\/p><\/blockquote>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>Equivariant frame \\(F(X)\\) is a disjoint union of equal size orbits, \\([g] \u2208 F(X)\/G_X\\).<\/p><\/blockquote>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Approximation of invariant frame averaging<\/strong><\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">When \\(F(X)\/G_X\\) is hard to enumerate, we can draw a random element from \\(F(X)\/G_X\\) with uniform probability.<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\"><p>Let \\(F(X)\\) be an equivariant frame, and \\(g \u2208 F(X)\\) be a uniform random sample. Then \\([g] \u2208 F(X)\/G_X\\) is also uniform.<\/p><\/blockquote>\n\n\n\n<p class=\"wp-block-paragraph\">Hence, we get an efficient approximation strategy that is averaging over uniform samples.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Model Instances<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">An instance of the FA framework contains:<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>The symmetry group \\(G\\), representations \\(\\rho_1,\\rho_2\\) , and the underlying frame \\(\\mathcal{F}\\).<\/li><li>The backbone architecture for \\(\\phi\\) (invariant) or \\(\\Phi\\) (equivariant).<\/li><\/ol>\n\n\n\n<h3 class=\"wp-block-heading\">Example: Normal Estimation with Point Cloud<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Here we use normal estimation with point cloud data as an example. The goal is to incorporate \\(E(d)\\) equivariance to the existing backbone architecture (e.g. PointNet and DGCNN).<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Mathematical Formulation<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">The paper proposed the frame \\(\\mathcal{F}(X)\\) based on <strong>Principal Component Analysis (PCA)<\/strong>. Formally, we present the centroid of \\(X\\) by<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">$$t=\\frac{1}{n}X^T\\mathbf{1}\\in\\mathbb{R}^d $$<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">$$t=\\frac{1}{n}X^T\\mathbf{1}\\in\\mathbb{R}^d $$<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">and covariance matrix computed after centering the data is<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">$$C=(X-\\mathbf{1}t^T)^T(X-\\mathbf{1}t^T)\\in\\mathbb{R}^{d\\times d} $$<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Then, we define the frame by<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">$$\\mathcal{F}(X)=\\{([\\alpha_1v_1, &#8230;, \\alpha_dv_d], t)|\\alpha_i\\in\\{-1, 1\\}\\}\\subset E(d) $$<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">where \\(\\mathbf{v}_1, &#8230;, v_d\\) are the eigenvectors of \\(C\\). From that, we can form the representation for the frames as transformation matrices.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">$$\\rho(g)=\\begin{pmatrix}R &amp; t \\\\\\mathbf{0}^T &amp; 1\\end{pmatrix}, R=\\begin{bmatrix}\\alpha_1v_1 &amp;&#8230;&amp;\\alpha_dv_d\\end{bmatrix} $$<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Implementation<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">We show part of the implementation of normal estimation for point cloud in PyTorch. For more details, please refer to the <a href=\"https:\/\/github.com\/omri1348\/Frame-Averaging\">open-source code<\/a> provided by the authors of [1]. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">We first perform PCA with the input point cloud.<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\n# Compute the centroid\ncenter = pnts.mean(1,True)\n# Center the points\npnts_centered = pnts - center\n# Compute covariance matrix\nR = torch.bmm(pnts_centered.transpose(1,2),pnts_centered)\n# Eigen-decomposition\nlambdas,V_ = torch.symeig(R.detach().cpu(),True)      \n# Reshape the eigenvectors   \nF =  V_.to(R).unsqueeze(1).repeat(1,pnts.shape&#091;1],1,1)\n\n<\/pre><\/div>\n\n\n<p class=\"wp-block-paragraph\">Then, we can construct the rotation matrices by<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\n# Write down permutations of alpha\nops = torch.tensor(&#091;\n\t&#091;1,1,1],\n    &#091;1,1,-1],\n    &#091;1,-1,1],\n    &#091;1,-1,-1],\n    &#091;-1,1,1],\n    &#091;-1,1,-1],\n    &#091;-1,-1,1],\n    &#091;-1,-1,-1]\n]).unsqueeze(1).to(point_cloud)\n\nF_ops = ops.unsqueeze(0).unsqueeze(2) * Frame.unsqueeze(1)\n\n<\/pre><\/div>\n\n\n<p class=\"wp-block-paragraph\">Finally, we perform the preprocessing to the point cloud data by centering and computing the frame average.<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\npnts_centered = point_cloud - center\n\n# Apply inverse of the frame operation\nframed_input = torch.einsum(&#039;bopij,bpj-&gt;bopi&#039;,F_ops.transpose(3,4),pnts_centered)\n\n# feed forward to the backbone neural network\n# e.g. point net\nouts = self.nn_forward(framed_input)\n\n# Apply frame operation\nouts = torch.einsum(&#039;bopij,bopj-&gt;bopi&#039;,F_ops,outs)\n\n# Take the average\nouts = outs.mean(1)\n\n<\/pre><\/div>\n\n\n<p class=\"wp-block-paragraph\">For a more detailed example application of frame averaging, please see the next blog post by our group: <em>Frame Averaging for Invariant Point Cloud Classification<\/em>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">[1] Omri Puny, Matan Atzmon, Heli Ben-Hamu, Ishan Misra, Aditya Grover, Edward J. Smith, and Yaron Lipman. Frame averaging for invariant and equivariant network design. In ICLR, 2022.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>written by Nursena Koprucu and Ruyu Yan Introduction In the first week of project SE(3) Invariant and Equivariant Neural Network for Geometry Processing, we studied the research approach frame averaging that tackles the challenge of representing intrinsic shape properties with neural networks. Here we introduce the paper Frame Averaging for Invariant and Equivariant Network Design[1] [&hellip;]<\/p>\n","protected":false},"author":5,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[142,143,141],"class_list":["post-805","post","type-post","status-publish","format-standard","hentry","category-research","tag-frame-averaging","tag-invariance-and-equivariance","tag-neural-network"],"_links":{"self":[{"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/posts\/805","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/comments?post=805"}],"version-history":[{"count":10,"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/posts\/805\/revisions"}],"predecessor-version":[{"id":1128,"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/posts\/805\/revisions\/1128"}],"wp:attachment":[{"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/media?parent=805"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/categories?post=805"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/summergeometry.org\/sgi2022\/wp-json\/wp\/v2\/tags?post=805"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}