基于邊緣特征的圖神經網絡架構搜索

周 鵬，楊 軍*，2

（1.蘭州交通大學 電子與信息工程學院，蘭州 730070；2.蘭州交通大學 測繪與地理信息學院，蘭州 730070）

以AlexNet［1］，GoogleNet［2］和RCNN［3］為代表的 人工設計神經網絡在圖像分類、分割和目標檢測等計算機視覺領域取得了很大成功.人工設計網絡架構需要進行不斷重復實驗，消耗了大量的人力和計算資源，且依賴專家經驗，專家需要重新設計算法適應新任務.因此，通過算法自動搜索出優秀的網絡架構逐漸成為該領域的研究熱點.神經網絡架構搜索（neural architecture search，NAS）旨在預定義的搜索空間中由搜索策略找到針對特定數據集的候選網絡架構，通過性能評估策略對候選架構進行評估，將評估結果反饋到搜索策略，再由搜索算法調整搜索策略，通過不斷重復搜索過程，直到發現最優的神經網絡架構.NAS在計算機視覺領域的表現已經達到，甚至超過人工設計的深度神經網絡，但仍需要耗費巨大的計算資源評估網絡架構.可微分架構搜索（differentiable architecture search，DARTS）［4］通過連續松弛化原有離散搜索策略，利用梯度下降法優化網絡架構，但離散化得到的子網與超網之間存在性能差距，子網需要重新訓練，導致搜索結果不穩定.文獻［5］對DARTS算法進行了改進，所提出的sharpDARTS引入余弦冪次退火算法對學習率進行更新，借助正則化方法糾正DARTS算法中的性能差距，降低了基于梯度算法消耗內存過大的問題；文獻［6］提出漸進式可微分結構搜索（progressive differentiable architecture search，P-DARTS）算法，使用搜索空間正則化來提高搜索的穩定性，并逐步增加網絡層數以減少內存消耗；文獻［7］提出連續貪婪策略搜索算法（sequential greedy architecture search，SGAS），優化了搜索過程和驗證過程準確率差異的問題.

近年來，研究者將NAS應用于圖機器學習領域，稱為圖神經網絡架構搜索（graph neural architecture search，GNAS）.文獻［8］首次用NAS算法來解決圖神經網絡（graph neural network，GNN）中的架構搜索，實現了基于強化學習的圖神經架構自動設計；文獻［9］提出邊緣特征圖注意力網絡，將圖神經網絡的使用擴展到具有節點和邊緣特征的任務，但該方法缺乏不同的更新函數來計算邊緣特征；NENN由節點級注意力層和邊緣級注意力層構建網絡模型，交替地將2種注意力層堆疊，并在相應的級別上學習節點和邊緣的特征［10］；文獻［11］提出索引邊緣幾何卷積神經網絡模型，將不同層的輸出特征映射并進行索引跳躍連接，使局部特征信息損失進一步降低.圖神經網絡的廣泛應用，使得基于復雜圖結構數據的任務，如點云分類、社會關系網絡分析、專家推薦系統及化學分子性質預測等問題得以高效解決，然而，GNN的可擴展性會導致計算成本增加，并隨著層級的深入呈指數增長，在對點云分類等大規模計算時挑戰巨大.

綜上所述，目前圖神經網絡架構搜索注重研究實體的特征信息，忽略了邊緣上的潛在高階信息與多層次關系特征之間的依賴，設計高效提取邊緣特征的圖神經網絡架構搜索空間與搜索算法，依然是一個需要研究的問題.本文提出邊緣特征圖神經網絡架構搜索（edge feature graph neural architecture search，EFGNAS）的方法，首先，在搜索空間中設計用于提取邊緣特征的候選操作，將邊緣與實體視為等價體，利用雙層優化方法同步更新實體和邊緣的高階信息，采用邊緣卷積同步提取局部和全局邊緣特征，以提高圖神經網絡架構的搜索性能；其次，設計基于邊緣特征的圖神經網絡架構搜索空間，用于實體和邊緣的更新；最后，提出基于邊緣特征提取的圖神經網絡搜索算法，采用雙層優化方法實現三維點云模型的分類.

1 搜索空間與搜索算法設計

本文采用邊緣卷積的方法提取三維點云特征，通過邊緣特征提取的方法對NAS的搜索空間進行優化設計，使用分組卷積提升搜索效率，并設計基于雙層優化的圖神經架構搜索算法.

1.1 點云特征提取

首先，計算全局點云特征.在三維點云中任選一點，計算以該點為中心的球形鄰域，通過迭代提取全局點云特征.其次，計算局部點云特征.采用邊緣卷積構造局部鄰域圖，在逐層卷積相鄰邊緣的過程中，輸出每一層在新特征空間的點云結構圖，得到一個新的局部區域；以中心點、中心點與鄰域點間距離為參數，計算點云局部特征.最后，由非對稱邊緣函數根據全局信息與局部信息計算三維點云邊緣特征.

設G=（v，ε）為點云結構圖，其中：v=｛v1，v2，…，vn｝表示點；ε表示邊.G中包含每個點的自循環，即每個點存在指向自身的邊.給定?vi，構造以vi為中心的球形鄰域N（vi），

其中：r表示鄰域半徑.當得到若干鄰域后，計算中心點vi的邊緣特征的輸出v′i，

其中：hθ（vi，vj）表示邊緣特征；hθ為包含可學習參數θ的非線性邊緣函數；Φ表示對邊緣特征進行通道對稱聚合.邊緣函數hθ與聚合操作Φ決定邊緣特征的輸出.針對三維點云特征提取，分為以下3種情況：

1）當hθ（vi，vj）=hθ（vi）時，表示對全局點云進行特征提取，不考慮局部鄰域結構.這種類型的特征提取方式在PointNet［12］中被使用，因此，可以看作是邊緣特征提取的一種特殊形式.

2）當hθ（vi，vj）=hθ（vj-vi）時，表示僅對局部點云進行特征提取，而不考慮全局結構.

3）當hθ（vi，vj）=hθ（vi，vj-vi）時，表示既考慮全局點云特征提取，又考慮局部鄰域信息，是本文采取的特征提取方式.

邊緣特征融合點間局部關系和全局信息，在得到若干個邊緣特征后，進行最大池化操作，得到該局部區域的單一特征，以這種方式進行多層卷積疊加，逐層提取并整合局部特征信息.

1.2 搜索空間設計

GNN可表示為使用消息傳遞機制工作的網絡，其每一層有一個聚合函數g和一個基于神經網絡的更新函數u.在圖G中，給定?vs表示序號為s的節點，χt-1s表示節點vs在時間步長t-1的特征，消息向量mts是由節點vs的鄰域點集Ns通過聚合函數計算得到，節點的特征χts由更新函數u和消息向量mts計算得到，如式（3）所示.

通過這種消息傳遞方式，在T層的GNN網絡中，消息以T個時間步長進行傳遞.該方法在處理結構化的二維圖像和序列化的信息等固定格式數據時非常有效，而對于數據量大、鄰域數據集多的大型圖結構，處理的效率和穩定性較低.為提高GNN在三維點云分類中的性能，本文采用網絡架構搜索的方式構建分類網絡.網絡架構搜索是一個逐步求精的過程，通過丟棄特征提取不佳的候選操作得到最優的網絡架構.

采用圖神經網絡的目的是尋找一種單元作為最終架構的構建模塊，每個單元是由M個節點的有序序列組成的有向無環圖（directed acyclic graph，DAG），每個節點之間的信息通過節點間的邊傳遞，每條邊包含若干候選操作和相應的網絡架構參數α，搜索空間中候選操作選擇流程如圖1所示.通常采用梯度下降的方法同時優化網絡架構參數α和權重參數ω，對α的優化可提高最終訓練的準確率，對ω的優化可以加快訓練準確率的提升，圖神經網絡架構搜索的最小單位稱為搜索單元（cell）.圖1（a）表示搜索算法需從搜索空間中選擇候選操作；圖1（b）中，搜索空間中有預先設計的諸多候選操作，由搜索策略組合不同的候選操作，再由評估策略對組合后的網絡架構進行性能評估，保留對性能提升貢獻大的候選操作，最終得到目標架構，如圖1（c）所示.

圖1 基于有向無環圖的神經網絡架構搜索決策過程Fig.1 Decision process of neural architecture search based on directed acyclic graph

在搜索空間中，采用的候選操作有rel_sage［7］，edge_conv［13］，mr_conv［14］，gat［15］，semi_gcn［16］，gin［17］，sage［18］，conv-1×1，skip-connect，EdgeConvDiff，EdgeGroupConv，EdgeGroupConvDiff，其中：conv-1×1是一個基本卷積操作；skip-connect表示跳躍連接操作；EdgeConvDiff，EdgeGroupConv與EdgeGroupConvDiff為本文新設計的候選操作，EdgeConvDiff為采用邊緣卷積提取三維點云全局特征，EdgeGroupConv為采用邊緣卷積提取三維點云局部特征，EdgeGroupConvDiff為采用邊緣卷積提取三維點云全局與局部特征，EdgeGroupConv與EdgeGroupConvDiff候選操作中引入了分組卷積和通道洗牌操作.

DAG圖中的每一個節點代表一個特征圖，用Vi表示，i為節點的序號，特征圖之間的連線表示候選操作，每一條連線都存在與相連節點相關的混合操作O（i，j），這些操作通過節點之間的關系特征E（i，j）將信息從Vi傳遞到Vj，如圖1中，V0為輸入，V3為輸出，V1，V2為中間節點，中間節點既是輸入節點，又是輸出節點，并攜帶上一步的狀態信息z，由前驅節點計算得到

其中：1≤j≤M.初始節點V0表示輸入一個實體信息，中間節點由輸入節點Vi、關系特征E（i，j）及狀態z經過混合操作O進行加權計算.

綜上所述，本文針對三維點云分類設計搜索空間.如圖2（a）所示，在搜索空間中，點云特征的提取基于圖卷積網絡，vi為中心點，vik表示vi的鄰域，eik為vi和vik構成的邊（k=1，2，…，n）；圖2（b）表示采用邊緣卷積的方法提取點云全局和局部特征，hθ為非線性邊緣函數.由于點云模型具有無序性、稀疏性、數據有限性等特點，使采用圖卷積網絡的處理效率不高.因此，為了提高點云的分類效率，本文采用組卷積方式對輸入的特征圖進行分組，如圖2（c）所示，共分為2組，每組分別卷積，再由通道洗牌操作促使特征信息跨特征通道傳遞；組卷積從不同組中獲取輸入數據，輸入和輸出通道完全相關；對于由前一組生成的特征映射，將每一組內的通道劃分為不同的子組，然后把不同的子組提供給下一層，這一過程由通道洗牌操作完成.通道洗牌是可微的，可以嵌入到網絡架構進行端到端訓練，這使得構建具有多組卷積層的網絡架構成為可能.

1.3 基于雙層優化的搜索算法

搜索空間A由不同的候選操作構成，旨在處理復雜的圖結構數據，傳遞不同類型的神經網絡消息.為提高GNN處理三維點云的效率和穩定性，本文采用基于雙層優化的自動架構搜索算法.GNAS可定義為一個雙層優化過程，在給定的圖搜索空間A中找到一個最優的神經網絡架構α*∈A，同時使驗證損失函數Lval（·）的值最小.通過使訓練損失函數Ltrain（·）最小化，得到與網絡架構相關的可訓練權重ω*，表示如下：

在DAG中，搜索算法根據預定義的選擇策略，在每一次迭代決策過程中，選擇一條邊，然后更新權重參數ω，當架構參數α值最大時，選擇對應的邊，同時裁剪掉局部α值最小時對應的邊；隨著裁剪的執行，剩余的參數將形成一個新的子問題，并進行迭代求解；在最后的搜索過程中，可以獲得一個獨立的無需共享權重架構.算法步驟如下：首先，定義GNAS的架構參數為α，網絡權重為ω，迭代次數為L，為抑制網絡過擬合，提高網絡的魯棒性和泛化能力，本文引入正則化方法規范架構參數的優化過程，定義正則化系數λl和正則化項rl，l∈｛1，2，…，L｝，正則化項rl通過計算架構參數指數和的對數后，再計算其平均值得出，用pytorch語言表示為rl=torch.mean（torch.logsumexp（self.model._arch_parameters，dim=-1））；其次，計算▽ALval（ω，α）+λlrl，以逐步更新網絡架構參數α，并且計算▽ωLtrain（ω，α），以逐步更新網絡權重ω，如果當前的迭代過程是決策過程，則選擇網絡架構參數α值最大時對應的邊，并在新選擇的邊上更新相關候選操作，再裁剪未被選中的網絡架構參數α和權重參數ω；最后，根據選擇到的候選操作組成目標架構.

2 仿真實驗與結果分析

2.1 在ModelNet10數據集上的搜索實驗

ModelNet［19］常用于三維模型分類，它包含ModelNet40和ModelNet10 2個數據集.ModelNet40含有40類12 311個CAD數據模型，其中：9 843個數據模型用于訓練；2 468個數據模型用于測試.Model-Net10是ModelNet40的子集，包含10類，共4 899個CAD數據模型，其中：3 991個模型用于訓練；908個模型用于測試.本文采用GNAS的網絡架構搜索方法，在ModelNet10數據集上進行搜索，在Model-Net40數據集上進行測試.

2.1.1 搜索空間參數設置

搜索空間的主干網絡由6個normal cell和2個reduction cell構成，其中：reduction cell位于網絡1/3和2/3處，其余為normal cell.設置normal cell的卷積層步長為1，reduction cell的卷積層步長為2.共有12個候選操作，如1.2節所述.

2.1.2 訓練參數設置

本文在ModelNet10數據集訓練和驗證，初始通道數設置為32個，采樣點為1 024個，初始cell數設置為2個，迭代次數設置為50次，輸入批量大小設置為32個，初始學習率的值為0.005，動量值為0.9，權重衰減值為3×10-4.采用隨機梯度下降（stochastic gradient descent，SGD）優化模型權重.設置初始迭代9次之后開始做決策選擇，每迭代7次做出一次搜索決策.由于硬件資源的局限性，批量值設置過大，會耗費更多的計算資源，達到相同準確率所需的迭代數量增多，同時梯度震蕩嚴重，不利于收斂；批量值設置過小，不同批量計算時梯度方向變化過小，容易陷入局部極小值.本文采用批量值動態調整策略，當出現搜索決策時，將批量值設置為“批量值+當前迭代次數”，從仿真實驗可以看出，該策略平均測試GPU時長為0.284 3 d，而消融實驗中平均測試GPU時長為1.027 2 d，采用該策略的訓練耗時大幅降低.

2.2 在ModelNet40數據集上的測試實驗

本文在ModelNet10數據集上，通過6個不同子實驗得到6個網絡架構，分別命名為EFGNAS_1，EFGNAS_2，EFGNAS_3，EFGNAS_4，EFGNAS_5和EFGNAS_6.在ModelNet40數據集上測試，搜索出6個網絡架構，得到三維點云分類的結果.將搜索的單元堆疊3次，采樣點為1 024個，通道數設置為128個，評估過程迭代次數設置為250次，批量大小設置為32個.使用Adam優化模型權重，權重衰減值為1×10-4，學習率的值為0.001.測試結果見表1.

從表1可以看出：在ModelNet10數據集上訓練時，網絡收斂快，隨著損失的穩步降低，訓練準確率逐步上升，最高達到97.24%，而驗證分類準確率最高為90.23%，測試分類準確率最高為93.42%.研究分類準確率與GPU時長、參數量的關系得知：在同樣的迭代次數下，最優網絡架構所對應的測試分類準確率與訓練和測試所耗費的GPU時長、參數量沒有直接的對應關系.

表1 EFGNAS在ModelNet數據集上的分類效果Tab.1 Classification accuracy of EFGNASon ModelNet

為了進一步說明本文算法的性能，圖3給出了EFGNAS的分類準確率與迭代次數的關系曲線圖.在圖3（a）中，模型的分類準確穩步提升，從訓練開始到第25次迭代，性能提升較快，在35～50次迭代中，前期表現較差的訓練過程分類準確率提升較快，逐步接近最佳分類準確率；由圖3（b）和圖3（c）可知，在驗證和測試過程中，前10次迭代的性能提升比較快，在11～15次迭代過程中，性能出現大幅下降，之后又出現逐步提升.可見，在數據量較小的ModelNet10數據集上，容易出現過擬合的情況，通過引入的正則化項后，在一定程度上抑制了過擬合的產生，保證了在小數據量模型時訓練的正常進行.

圖3 EFGNAS在訓練、驗證與測試中的分類準確率與迭代次數關系曲線圖Fig.3 Plot of classification accuracy with iterations in training，validation and testing by EFGNAS

圖4為搜索出來的6個網絡架構的圖形化表示，其中：c_｛k｝為所有中間節點的深度連接，表示當前網絡架構的輸出；c_｛k-1｝和c_｛k-2｝分別表示第k-1，k-2個網絡架構的輸出.從圖4可以看出：搜索結果中均出現本文所設計的EdgeConvDiff，EdgeGroupConv與EdgeGroupConvDiff等候選操作；測試分類準確率前3位分別為圖4（a）、圖4（c）和圖4（f）的網絡結構，新設計的候選操均出現2次，在圖4（d）中出現3次，但圖4（d）所對應的網絡架構測試分類準確率并不是最高，可見架構性能的優劣和整體架構中所有候選操作及其構成方式有很大關系.

圖4 EFGNAS生成架構的圖形化表示Fig.4 Gaphing of the searched architecture by EFGNAS

EFGNAS與人工設計的網絡架構、自動搜索的架構在三維點云模型上的分類準確率、參數量和所需GPU時長對比結果見表2，其中：manual表示人工設計的網絡架構.

由表2可知：本文方法EFGNAS（最佳值）與SGAS相比，參數量增加0.044 3 MB，所占用的GPU時長比SGAS減少0.031 2 d，分類準確率提升了1.42%，由于SGAS算法搜索空間中的候選操作沒有考慮到分組卷積和邊緣特征的提取，影響了分類準確率的提升；與RBNAS相比，本文方法EFGNAS（最佳值）的分類準確率提高了0.32%，參數量減少了0.204 3 MB，GPU時長增加了0.108 8 d，原因是RBNAS算法資源平衡型漸進式剪枝的思路存在對漸進系數的過分依賴；與NoisyDARTS相比，本文方法EFGNAS（最佳值）的分類準確率提高了0.52%，參數量減少了4.574 3 MB，GPU時長增加了0.118 8 d，原因是NoisyDARTS在候選操作中添加了噪聲，使候選操作之間公平競爭，特別是對跳躍連接的過快增長起到了一定的抑制作用，但是與選擇的噪聲及特定的數據集密切相關，且泛化能力較弱；本文在SGAS的基礎上，采用邊緣卷積的方法提取了點云的全局特征與局部特征，同時，為降低引入圖卷積導致計算成本的增加，采用分組卷積的方法提升了搜索效率，本算法的平均分類準確率EFGNAS（平均值）為92.56%，最佳分類準確率EFGNAS（最佳值）為93.42%，搜索到的最佳網絡架構取得了較低的GPU運行時長和參數量，且分類準確率高于目前常見的人工設計和自動搜索的網絡架構，說明采用邊緣卷積的方法能提取更豐富的點云特征.

表2 本文方法與其他方法在三維模型分類上的比較Tab.2 Comparison with the proposed method with other methods in three-dimensional classification

2.3 消融實驗

為進一步驗證采用邊緣特征提取的方法對分類準確率的影響，本文完成了未進行邊緣特征提取的實驗，實驗名稱為EFGNAS*.實驗所得到的分類準確率、訓練GPU時長、測試GPU時長和參數量見表3.從表1和表3可看出：EFGNAS（最佳值）測試分類準確率較EFGNAS*（最佳值）提高了1.12%，尤其在測試GPU時長方面，較EFGNAS*降低了74%，因此，本文算法有效提升了搜索效率，且在測試分類準確率有一定提升的前提下，網絡參數量和GPU運行時長降低顯著.

表3 EFGNAS*在ModelNet數據集上的分類效果Tab.3 Classification accuracy of EFGNAS*on ModelNet

圖5為EFGNAS*在訓練、驗證與測試中的分類準確率與迭代次數關系曲線圖.如圖5（a）所示，EFGNAS*在訓練過程中，分類準確率上升比較平穩，6次訓練中，最高分類準確率為97.02%，比EFGNAS低0.22%，從開始訓練到迭代10次，性能提升較快.其中：3次訓練過程分類準確率較低，在迭代的中后期，雖然性能有一定提升，但仍與最高分類準確率存在差距，而EFGNAS前期性能提升較慢的訓練過程在迭代的中后期提升較快，接近最高分類準確率.由圖5（b）和圖5（c）可知：EFGNAS*的驗證分類準確率和測試分類準確率在剛開始到第10次迭代過程中準確率提升較快，之后出現大幅下降，且后期提升緩慢.對比圖3（b）和圖3（c）可知：本算法魯棒性較強，能有效抑制過擬合，分類準確率上升平穩.

圖5 EFGNAS*在訓練、驗證與測試中的分類準確率與迭代次數關系曲線圖Fig.5 Plot of classification accuracy with iterations in training，validation and testing by EFGNAS*

表4對比了EFGNAS和EFGNAS*分類準確率的排序.

表4 2種不同網絡模型在訓練、驗證和測試中分類準確率的排序Tab.4 Classification accuracy rank of two different network models in training，validation，and testing

將排序表示為肯德爾相關性系數時可以分析出不同排序的相關性.肯德爾相關系數又稱和諧系數，是一個用來測量2個隨機變量排序相關性的統計值，表示為

其中：c為所對比的2個序列中擁有一致性的元素對數；d表示序列中擁有不一致性的元素對數；n表示樣本量表示所有樣本兩兩組合的數量.一個肯德爾檢驗是一個無參數假設檢驗，它使用計算所得的相關系數去檢驗2個隨機變量的統計依賴性.τ的取值范圍為［-1，1］，當τ為1時，表示2個隨機變量擁有一致的等級相關性；當τ為-1時，表示2個隨機變量擁有完全相反的等級.理想的NAS算法應該具有較高的搜索-測試肯德爾相關性系數τ.

本實驗對比EFGNAS和EFGNAS*的訓練階段、驗證階段和測試階段的肯德爾相關系數.表5為EFGNAS和EFGNAS*分類準確率排序的肯德爾相關系數值，由訓練階段、驗證階段和測試階段的分類準確率排名計算所得.從表5和式（6）可知：EFGNAS訓練階段與驗證階段分類準確率的τ值為0.333 3，EFGNAS*訓練階段與驗證階段分類準確率的τ值為0.200 0；EFGNAS訓練階段與測試階段分類準確率的τ值為0.600 0，而EFGNAS*訓練階段與測試階段分類準確率的τ值為-0.066 7.以上數據說明EFGNAS在訓練階段和驗證階段、訓練階段和測試階段均具有較高的相關性，同時也證明了EFGNAS模型的魯棒性較強.

表5 EFGNAS和EFGNAS*分類準確率肯德爾相關性系數Tab.5 Comparison of search-evaluation Kendall coefficients and classification accuracy by EFGNAS＆EFGNAS*

3 結論

針對目前大多數圖神經網絡注重研究對象實體特征信息、忽略與邊相關的特征信息的問題，本文提出了基于邊緣特征提取的架構搜索算法自動設計網絡架構.首先，提出了邊緣特征圖神經網絡架構搜索的方法，設計了基于邊緣特征的搜索空間和搜索算法；其次，將邊緣與實體視為等價體，利用雙層優化方法對實體信息和邊信息進行了更新，采用邊緣卷積和通道洗牌操作，在有限的計算資源下，獲得了最佳的模型分類精度，并在速度和精度之間取得良好的平衡；最后，通過三維點云分類的實驗，對所提出的方法進行了驗證.仿真實驗結果表明：本文所提出的方法能提升網絡架構搜索算法的效率，防止網絡過擬合，提高三維點云分類準確率，具有較強的魯棒性.總的來說，目前圖神經網絡架構搜索取得了一定的效果，但在處理深層網絡結構、大規模數據時，其適應性、可擴展性和效率方面仍有很大的改進空間.