1
本文作者: 楊文 | 2017-12-20 18:44 |
雷鋒網(wǎng)AI科技評論按:網(wǎng)絡(luò)是大數(shù)據(jù)的重要組織形式,然而網(wǎng)絡(luò)化的數(shù)據(jù)由于缺少高效可用的節(jié)點表示,而難于直接應(yīng)用。網(wǎng)絡(luò)化數(shù)據(jù)表示學(xué)習通過將高維稀疏難于應(yīng)用的數(shù)據(jù)轉(zhuǎn)化為低維緊湊易于應(yīng)用的表達而受到廣泛關(guān)注。網(wǎng)絡(luò)化數(shù)據(jù)表示學(xué)習的一個重要任務(wù)就是重疊社區(qū)發(fā)現(xiàn)。本文就是為大家介紹基于網(wǎng)絡(luò)化數(shù)據(jù)表示學(xué)習的重疊社區(qū)發(fā)現(xiàn)的最新研究。文章內(nèi)容根據(jù)中科院孫冰杰博士在雷鋒網(wǎng)GAIR大講堂的線上直播公開課整理而成。
在近日雷鋒網(wǎng) GAIR 大講堂線上直播課上,來自中科院計算所網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點實驗室的孫冰杰博士為大家做了一場主題為「基于網(wǎng)絡(luò)化數(shù)據(jù)表示學(xué)習的重疊社區(qū)發(fā)現(xiàn)研究」的分享,詳細介紹了他們團隊最近在基于網(wǎng)絡(luò)化數(shù)據(jù)表示學(xué)習的重疊社區(qū)發(fā)現(xiàn)研究上的相關(guān)工作。
孫冰杰,中科院計算所博士研究生,主要研究方向為網(wǎng)絡(luò)結(jié)構(gòu)分析,網(wǎng)絡(luò)表示學(xué)習。
分享內(nèi)容:
我將從以下四個方面對我們團隊最近所做的研究做詳細介紹。
研究背景及挑戰(zhàn)
對稱編解碼重疊社區(qū)發(fā)現(xiàn)方法:SEND
重疊社區(qū)發(fā)現(xiàn)方法加速研究
總結(jié)
首先看我們研究工作的背景及挑戰(zhàn)。
大數(shù)據(jù)領(lǐng)域中大部分數(shù)據(jù)是以網(wǎng)絡(luò)形式進行組織的,比如社交媒體中的社交網(wǎng)絡(luò),科研領(lǐng)域中的引用網(wǎng)絡(luò),生物領(lǐng)域的中蛋白質(zhì)相互作用網(wǎng)絡(luò),以及交通領(lǐng)域中的航空網(wǎng)路或路網(wǎng)。網(wǎng)絡(luò)化數(shù)據(jù)之后節(jié)點之間的復(fù)雜關(guān)系是導(dǎo)致大數(shù)據(jù)處理困難的重要原因。
網(wǎng)絡(luò)化數(shù)據(jù)在不同粒度下對應(yīng)的理論與應(yīng)用研究也是不同的。在微觀粒度上,主要研究的是節(jié)點層面上的任務(wù),當節(jié)點聚集形成社區(qū)的時候,研究的是社區(qū)層面上的任務(wù)。在宏觀層面上,我們研究的是在整個網(wǎng)絡(luò)上的任務(wù)。
在這次分享上,我們主要研究在中觀粒度下的社區(qū)發(fā)現(xiàn)任務(wù)。它主要由三元閉包理論和強弱連接理論為支撐,主要支撐的應(yīng)用有社區(qū)發(fā)現(xiàn)應(yīng)用等。
中觀粒度上的社區(qū)發(fā)現(xiàn)任務(wù):向下可通過節(jié)點表示支持微觀粒度的任務(wù),向上可通過網(wǎng)絡(luò)生成支持宏觀粒度的任務(wù)。
基于網(wǎng)絡(luò)化數(shù)據(jù)表示學(xué)習的重疊社區(qū)發(fā)現(xiàn)所面臨的問題和挑戰(zhàn)
相對于傳統(tǒng)節(jié)點表示,它的功能是比較單一的,只支持重疊社區(qū)指示,無法支持一些其他的任務(wù)。但現(xiàn)有的重疊社區(qū)指示方法沒辦法用在大規(guī)模網(wǎng)絡(luò)上。這是針對社區(qū)指示能力和多任務(wù)支持能力之間的矛盾以及海量數(shù)據(jù)處理任務(wù)的挑戰(zhàn)。
為此我們團隊做了兩方面的工作。
工作一:非負對稱編解碼模型
節(jié)點表示的社區(qū)指示能力需要滿足多種約束條件。一般需要滿足三個約束條件,非負性,稀疏性和分布性。
節(jié)點表示的多任務(wù)支持能力
需要節(jié)點表示能充分恢復(fù)數(shù)據(jù)在原始空間中的相似性關(guān)系,對節(jié)點表示添加的約束越多,對數(shù)據(jù)的恢復(fù)能力影響越大。因此這之間是矛盾的。矛盾主要體現(xiàn)在基于網(wǎng)絡(luò)化數(shù)據(jù)表示的社區(qū)發(fā)現(xiàn)相關(guān)工作。
工作一是針對重疊社區(qū)得到節(jié)點表示的社區(qū)表示能力和數(shù)據(jù)還原能力之間的矛盾。目標是保證節(jié)點表示的社區(qū)指示能力和對原始數(shù)據(jù)的還原能力。
所面臨的問題:
如何在數(shù)據(jù)恢復(fù)過程中對節(jié)點表示進行約束增加指示能力。
傳統(tǒng)的OCD只優(yōu)化解碼過程,節(jié)點表示功能單一,不能應(yīng)用于其他任務(wù)。
OCD節(jié)點表示的顯示約束使優(yōu)化困難
解決方案:用戶點表示同時對原始數(shù)據(jù)進行編解碼操作,保證學(xué)習到高質(zhì)量節(jié)點表示。通過編解碼過程對對稱性節(jié)點表示進行隱式約束,保證指示能力。
具體來說,OCD模型通過重構(gòu)輸入數(shù)據(jù)學(xué)習節(jié)點表示,通過正則項等對節(jié)點表示進行顯式約束,保證節(jié)點表示的指示能力。但傳統(tǒng)的OCD目標函數(shù)相當于只優(yōu)化了解碼過程(生成原始數(shù)據(jù))
OCD目標函數(shù)忽略了編碼過程,導(dǎo)致模型學(xué)習到的節(jié)點表示無法充分體現(xiàn)節(jié)點在原空間中的相似性,因此應(yīng)用在下游任務(wù)上準備性較低,且無法處理新樣本數(shù)據(jù)。
以上提出的對稱編解碼模型可以同時解決節(jié)點表示的指示能力和對多種下游任務(wù)的支持能力。
通過優(yōu)化編碼和解碼過程保證節(jié)點表示的數(shù)據(jù)還原能力,通過隱式約束保證節(jié)點表示的社區(qū)表示能力,從而最終在多種類型網(wǎng)絡(luò)的多個任務(wù)上取得了目前最好的效果。
進一步介紹這個模型的普適性,我們希望這個節(jié)點表示能夠用在更多的任務(wù)上。因此我們采用了多種類型的網(wǎng)絡(luò),比如說二部網(wǎng)絡(luò),有向網(wǎng)絡(luò)、有權(quán)網(wǎng)絡(luò)、層次網(wǎng)絡(luò)等,也采用了多種類型輸入,比如說節(jié)點序列輸入,鄰接矩陣輸入等。
工作小結(jié):本文工作針對重疊社區(qū)發(fā)現(xiàn)得到的節(jié)點表示存在的“指示能力和多任務(wù)支持”之間的矛盾,設(shè)計了一種同時優(yōu)化編解碼過程的模型,可以保證節(jié)點表示的指示能力并且在多種類型網(wǎng)絡(luò)的多個任務(wù)上取得了最好的效果。
工作二:重疊社區(qū)發(fā)現(xiàn)方法加速研究
現(xiàn)有的重疊社區(qū)發(fā)現(xiàn)方法存在“速度與精度”之間的矛盾,在面臨大規(guī)模網(wǎng)絡(luò)時,無法拿來急用。
關(guān)于問題一,如何選擇高質(zhì)量的參數(shù)迭代初始點。提出利用一個與非凸目標函數(shù)近似的凸目標函數(shù)的優(yōu)化結(jié)果作為非凸目標函數(shù)優(yōu)化的迭代初始點,以保證最終速度和效果。
重疊社區(qū)發(fā)現(xiàn)的模型選擇
關(guān)于問題二,解決由迭代過程的復(fù)雜性帶來的優(yōu)化困難問題。傳統(tǒng)的應(yīng)對迭代過程復(fù)雜性的方法是采樣和近似。這類方法是影響精度且仍然不夠快。
解決方案:網(wǎng)絡(luò)結(jié)構(gòu)局部聚集特性和節(jié)點表示的稀疏性,相應(yīng)地設(shè)計了“維度級”和“連邊級”兩級加速策略,對模型進行加速。
工作小結(jié):針對基于泊松模型的重疊社區(qū)發(fā)現(xiàn)方法,目標函數(shù)的非凸性和迭代過程的復(fù)雜性,提出了兩種加速策略,分別解決了初始點選擇問題和迭代過程復(fù)雜問題??梢蕴幚碚鎸嵈笠?guī)模網(wǎng)絡(luò)。
綜上所述:針對重疊社區(qū)發(fā)現(xiàn)任務(wù),我們主要解決了三個問題。編解碼模型解決了重疊社區(qū)發(fā)現(xiàn)得到的節(jié)點表示的社區(qū)指示能力和數(shù)據(jù)恢復(fù)能力之間的矛盾??焖俪踔的P徒鉀Q了目標函數(shù)非凸性帶來的可擴展性問題。兩級加速模型解決了優(yōu)化過程復(fù)雜性帶來的可擴展性問題。
視頻回放鏈接:http://www.mooc.ai/open/course/357
雷峰網(wǎng)原創(chuàng)文章,未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。