算法思想

2021-10-09_17-04.png

參考資料

https://zhuanlan.zhihu.com/p/45167021

代碼實現(xiàn)與注解

思路

• 理清successor，outdegree函數(shù)的輸入輸出
• 查看補全函數(shù)的返回類型--分析可能的結(jié)果--我最初的猜測：這walks應(yīng)該是多個向量的集合，最后確實也是【[[],..]這樣的結(jié)構(gòu)多用于擴充，然后聯(lián)想需要學習向量，所以想到向量遞推的那種向量集合】
• 生成隨機采樣索引序列集 -- 這個需要匹配采樣形狀，以及索引閾值--我是參考一個示例修改的，感悟是: 利用隨機數(shù)0~1，給rand傳入指定shape，再乘以一個相同shape的數(shù)據(jù)，可以得到一個>=0, <=最大出度-1的值，這樣就可以用來索引采樣了
• 理清上下文變量關(guān)系，進行zip打包遍歷到一起，然后進行聚合操作即可。

Code

%%writefile userdef_graph.py
from pgl.graph import Graph

import numpy as np


class UserDefGraph(Graph):
    def random_walk(self, nodes, walk_len):
        """
        輸入：nodes - 當前節(jié)點id list (batch_size,)
             walk_len - 最大路徑長度 int
        輸出：以當前節(jié)點為起點得到的路徑 list (batch_size, walk_len)

        用到的函數(shù)
        1. self.successor(nodes)
           描述：獲取當前節(jié)點的下一個相鄰節(jié)點id列表
           輸入：nodes - list (batch_size,)
           輸出：succ_nodes - list of list ((num_successors_i,) for i in range(batch_size))
        2. self.outdegree(nodes)
           描述：獲取當前節(jié)點的出度
           輸入：nodes - list (batch_size,)
           輸出：out_degrees - list (batch_size,)
        """
        # 首先獲得當前節(jié)點列表對應(yīng)的一個向量
        walks = [[node] for node in nodes]
        # 游走路徑中節(jié)點對應(yīng)id號
        walks_ids = np.arange(0, len(nodes))
        # 當前節(jié)點情況
        cur_nodes = np.array(nodes)
        # 根據(jù)游走長度進行遍歷--破出條件：1. range結(jié)束；2. outdegree==0【出度為零，沒有可繼續(xù)的節(jié)點】
        for l in range(walk_len):
            """選取有下一個節(jié)點的路徑繼續(xù)采樣，否則結(jié)束"""
            # 計算當前節(jié)點的出度--也就是對應(yīng)有哪些位置的鄰近節(jié)點
            outdegree = self.outdegree(cur_nodes)
            # 根據(jù)出度來確定掩碼--True， False--將出度為0的部分復(fù)制為False，反之True
            walk_mask = (outdegree != 0)
            # 判斷是否沒有可繼續(xù)的節(jié)點情況--出度為0
            if not np.any(walk_mask):
                break
            # 根據(jù)掩碼獲取可繼續(xù)前進的節(jié)點，作為后邊討論的當前可前行節(jié)點
            cur_nodes = cur_nodes[walk_mask]
            # 獲取掩碼下，原節(jié)點id，組成新的work_ids用于后邊討論，但本身還是作為一個節(jié)點的標記，對應(yīng)這是第幾個節(jié)點
            walks_ids = walks_ids[walk_mask]
            # 根據(jù)掩碼獲取相應(yīng)的不為0的出度--用于后邊計算前行的路徑
            outdegree = outdegree[walk_mask]
            # 返回可繼續(xù)的節(jié)點集合 successor 可獲取當前節(jié)點的下一個相鄰節(jié)點id列表，
            # 那么successor 計算出下一節(jié)點的集合后，我們需要從中隨機取出一個節(jié)點--所以我們要創(chuàng)建隨機采樣的index_list（索引序列集）
            succ_nodes = self.successor(cur_nodes)
            # 創(chuàng)建index_list=>為了才到合適的index信息，采用np.floor與np.random,rand()實現(xiàn)：
            # eg: np.floor(np.random.rand(outdegree.shape[0]) * outdegree).astype('int64')
            # np.random.rand(outdegree.shape[0]): 根據(jù)出度集的形狀來取得相應(yīng)形狀的隨機數(shù)--這里體現(xiàn)游走的隨機性
            # np.random.rand(outdegree.shape[0]) * outdegree：利用生成的隨機數(shù)與出度集對應(yīng)元素相乘——這里得到一些列的隨機數(shù)
            # 隨機數(shù)范圍在0~最大出度值--保證路徑有效
            # np.floor(np.random.rand(outdegree.shape[0]) * outdegree)——實現(xiàn)向下取整，這樣就得到了相應(yīng)游走路徑中接下來那個點的索引
            sample_index = np.floor(np.random.rand(outdegree.shape[0]) * outdegree).astype('int64')
            """
            具體實例：
            np.floor(np.random.rand(20) * 3).astype('int64')
            result: array([0, 1, 2, 1, 0, 0, 0, 0, 1, 1, 1, 2, 0, 2, 2, 2, 2, 1, 2, 0])
            """
            # 知道了隨機采樣的序列集了，那么接下就是分配新的游走路徑了
            # 用于后邊存放—— 裝配有下一個節(jié)點的新路徑
            next_nodes = []
            # succ_nodes：相鄰節(jié)點id列表
            # sample_index：對應(yīng)出度生成的隨即索引集
            # walks_ids：游走路徑中節(jié)點對應(yīng)id號
            for s, ind, walk_id in zip(succ_nodes, sample_index, walks_ids):
                # 將節(jié)點列表、隨機采樣序列、游走路徑中節(jié)點對應(yīng)id號一一對應(yīng)進行填充
                # 為相應(yīng)節(jié)點添加可以繼續(xù)前行的節(jié)點，形成一條路徑
                walks[walk_id].append(s[ind])# walks=>[[], [], []]是這種形式的
                # 同時獲取接下來要重新討論游走時所需的新節(jié)點
                next_nodes.append(s[ind])
                """
                如：從1走到了2，從3走到了7: [[1], [3]]=>[[1, 2], [3, 7]]     
                next_nodes.append(s[ind])        
                # 接下來自然就該考慮把新的2, 7 作為下一次游走時討論出度的節(jié)點啦
                """
            cur_nodes = np.array(next_nodes)  # 將節(jié)點轉(zhuǎn)換為np類型，方便一些操作運算--同時保證前后數(shù)據(jù)類型
            # 并且list中，元素本質(zhì)是對象。如：L = [1, 2, 3]，需要3個指針和三個整數(shù)對象，對于數(shù)值運算比較浪費內(nèi)存和CPU
            # Numpy提供了ndarray(N-dimensional array object)對象：存儲單一數(shù)據(jù)類型的多維數(shù)組。
        # 遍歷完游走長度的次數(shù)，就可以返回得到的隨機游走路徑啦
        return walks

print(np.floor(np.random.rand(20) * 3).astype('int64'))