Paper Code Introduction 无监督图学习算法基于重构损失，不可避免的需要图相似度计算（重构embedding和输入embedding的loss), 计算复杂度较高。本文提出一种通用的归纳式无监督图学习算法SEED（Sampling, Encoding, and Embedding Distributions）。通过计算采样子图的重构损失来代替整个图的重构损失。 即 先采样子图，在用GNN编码子图，最后计算子图分布的embedding来作为整个图的representation. 过程如下图所示： SEED: Sampling, Encoding, and Embedding Distributions Anonymous Random Walk Definition 1 (Random Anonymous Walks[1]): Given a random walk $\mathbf{w}=(w_1, \cdots, w_l)$ where $\langle w_i, w_{i+1} \rangle \in E$, the anonymous walk for $\mathbf{w}$ is defined as： $$ \mathrm{aw}(\mathbf{w}) = (\mathrm{DIS}(\mathbf{w}, w_1),\mathrm{DIS}(\mathbf{w}, w_2),\cdots, \mathrm{DIS}(\mathbf{w}, w_l) ) $$ where $\mathrm{DIS}(\mathbf{w}, w_i)$ denotes the number of distinct nodes in $\mathbf{w}$ when $w_i$ first appears in $\mathbf{w}$, i.e. $$ \mathrm{DIS}(\mathbf{w}, w_i) = |{w_1, \cdots w_p}|, \quad p = \min_j {w_j=w_i} $$ 匿名随机游走和随机游走的不同在于，匿名随机游走描述了随机游走的潜在“patterns”, 不管具体被访问的节点是什么。 距离来说，给定两条随机游走序列 $\mathbf{w_1}=(v_1, v_2, v_3, v_4, v_2)$ 和$w_2=(v_2, v_1, v_3, v_4, v_1)$, 这两个RW相关联的匿名随机游走是一样的，即$\mathrm{aw}(\mathbf{w_1}) = \mathrm{aw}(\mathbf{w_2}) = (1,2,3,4,2)$, 即使$\mathbf{w_1}$和$\mathbf{w_2}$访问不同的节点。即每个节点在RW中首次被访问时的位置就是这个点在ARW中的id,如在$\mathbf{w_2}$中，$v_1$首次访问是在第二个时刻，那么他的id就是2，在ARW中用2表示。 ...

晕了 import networkx as nx import matplotlib.pyplot as plt n_clique, n_path = 10, 10 clique1 = nx.complete_graph(n_clique) clique1_pos = nx.circular_layout(clique1) clique2 = nx.complete_graph(n_clique) clique2_mapping = {node: node + n_clique for node in clique2} nx.relabel_nodes(clique2, clique2_mapping, copy=False) # avoids repeated nodes x_diff, y_diff = 8, -1 clique2_pos = {node: clique1_pos[node-n_clique] + (x_diff, y_diff) for node in clique2} path = nx.path_graph(n_path) path_mapping = {node: node + 2 * n_clique for node in path} nx.relabel_nodes(path, path_mapping, copy=False) # avoids repeated nodes path_nodes = list(path.nodes) path_half1_nodes = path_nodes[:n_path//2] path_half2_nodes = path_nodes[n_path//2:] path_dist = 0.9 clique2_entry = n_clique + n_clique // 2 path_half1_pos = {node: clique1_pos[0] + (path_dist + i * path_dist, 0) for i, node in enumerate(path_half1_nodes)} path_half2_pos = {node: clique2_pos[clique2_entry] - (path_dist + i * path_dist, 0) for i, node in enumerate(path_half2_nodes[::-1])} path_pos = {**path_half1_pos, **path_half2_pos} barbell = nx.Graph() barbell.add_edges_from(clique1.edges) barbell.add_edges_from(clique2.edges) barbell.add_edges_from(path.edges) barbell.add_edges_from([(path_half1_nodes[0], 0), (path_half2_nodes[-1], clique2_entry)]) clique_pos = {**clique1_pos, **clique2_pos} barbell_pos = {**clique_pos, **path_pos} plt.figure(figsize=(20, 6)) nx.draw(barbell, pos=barbell_pos, with_labels=True) ...

Mean Discrepancy (MD)均值差异 判断2个分布$p$ 和$q$是否相同。 $p$分布生成一个样本空间$\mathbb{P}$ (从$p$中采样$m$个样本) $q$分布生成一个样本空间$\mathbb{Q}$（从$q$中采样$n$个样本） 函数$f$的输入为 分布生成的样本空间 如果 $$ \begin{equation} \begin{aligned} \mathrm{mean}(f(\mathbb{P})) == \mathrm{mean}(f(\mathbb{Q})) \\ i.e., \frac{1}{m}\sum^m_{i=1}f(p_i) = \frac{1}{n}\sum^n_{i=1}f(q_i) \end{aligned} \end{equation} $$ 则$p$和$q$是同一分布。 MD can be defined as $$ \begin{equation} \begin{aligned} \mathrm{MD}&=|\mathrm{mean}(f(\mathbb{P})) -\mathrm{mean}(f(\mathbb{Q})) | \\ &= |\frac{1}{m}\sum^m_{i=1}f(p_i) - \frac{1}{n}\sum^n_{i=1}f(q_i)| \end{aligned} \end{equation} $$ Maximum Mean Discrepancy (MMD) 最大均值差异 定义 MMD: 在函数集$\mathcal{F}=\{f_1, f_2, \cdots \}$中， 找到一个函数$f^*$， 使得$|\mathrm{mean}(f^*(\mathbb{P})) -\mathrm{mean}(f^*(\mathbb{Q})) |$ 最大。 这个最大值就是两个分布之间的最大均值差异（MMD）。MMD =0 表示两个分布相同。 $$ \operatorname{MMD}[\mathcal{F}, p, q]:=\sup _{f \in \mathcal{F}}\left(\mathbf{E}_{x \sim p}[f(x)]-\mathbf{E}_{y \sim q}[f(y)]\right) $$ 其中$\mathbf{E}_{x \sim p}[f(x)]$表示分布$p$在函数$f$下的均值， $\sup$为上确界直接理解为max就好。 ...

Hilbert Space Definition 1 (Norm) Let $\mathcal{F}$ be a vector space over $\mathbb{R}$ (For example $\mathcal{F}=\mathbb{R}^n$ is a vector space). A function $||\cdot||_{\mathcal{F}}: \mathcal{F} \to [0, \inf)$ is said to be a norm on $\mathcal{F}$ if ($||\cdot||_{\mathcal{F}}$ 是一个有效norm算子要满足以下条件): For $f \in \mathcal{F}$, $||f||_{\mathcal{F}}=0$ if and only if $f=0$. (norm separates points) $|\lambda f|_{\mathcal{F}}=|\lambda||f|_{\mathcal{F}}$, $\forall \lambda \in \mathbb{R}, \forall f \in \mathcal{F}$ (positive homogeneity). $|f+g|_{\mathcal{F}} \leq|f|_{\mathcal{F}}+|g|_{\mathcal{F}}, \forall f, g \in \mathcal{F}$ (triangle inequality). 向$||\cdot||_{\mathcal{F}}$中输入任意一个向量，只要满足以上条件，那么$||\cdot||_{\mathcal{F}}$是一个valid norm operator. ...

单一状态Monte Carlo规划：多臂赌博机（Multi-armed bandits） 单一状态$s$, $k$种action（$k$个摇臂）。 在摇臂赌博机问题中，$s$每次以随机采样形式采取一种行动$a$。 例如，随机拉动第$k$个赌博机，得到的reward为$R(s, a_k)$。问下一次拉动哪个赌博机，才能获得最大Reward? 多臂赌博机问题是一种序列决策问题，这种问题需要在利用（exploitation）和探索（exploration）之间保持平衡。 利用（Exploitation）： 保证在过去决策中得到最佳回报 探索（Exploration）：寄希望在未来能够得到更大的汇报 例如， $s$摇动10次赌博机，其中第5次获得最大回报，那么下一次摇动赌博机可能选第5个赌博机，即“利用”（根据过去的最佳回报来施展下一次行为），第11次摇动的action为$a_5$。 但是摇动10次后，可能有的赌博机尚未摇动，未摇动的赌博机可能会有更大回报，即“探索”。 悔值函数 如果有$k$个赌博机， 这$k$个赌博机产生的操作序列为$X_{i,1}, X_{i,2}, \cdots (i = 1,\cdots, k)$。 在时刻$t=1,2,\cdots$, 选择第$I_t$个赌博机后，可得到的奖励为$X_{I_t,t}$, 则在$n$次操作$I_1,\cdots,I_n$后，可如下定义悔值函数： $$ R_n = \max_{i=1,\cdots,k} \sum^n_{t = 1} X_{i,t}-\sum^n_{t=1}X_{I_t, t} $$ $i$: 第$i$个赌博机 $I_t$: $t$时刻选择的赌博机 $\max_{i=1,\cdots,k} \sum^n_{t = 1} X_{i,t}$: 最理想（大）的奖励 $X_{I_t, t}$: $t$时刻选择赌博机$I_t$的reward $\sum^n_{t=1}X_{I_t, t}$: $n$次选择的总奖励。 $R_n$越大，就代表$n$次决策的结果越差。 上置信区间（Upper Confidence Bound, UCB） UCB旨在探索和利用间去的平衡 在UCB方法中，使$X_{i, T_{i}(t-1)}$ 来记录第$i$个赌博机在过去$t-1$时刻内的平均奖励，则在第$t$时刻，选择使如下具有最佳上限置信区间的赌博机： $$ I_{t}=\max_{i \in{1, \ldots, k}}\left\{\overline{X_{i, T_{i}(t-1)}}+C_{t-1, T_{i}(t-1)} \right\}. $$ 其中$I_{t}$为$t$时刻要摇的赌博机， ...

论文地址： DiffPool Introduction 传统的GNN算法在Node-level的任务如节点分类、链路预测上有着较好的效果。但是，现有的GNN方法由于其存在平面化的局限性，因此无法学习图的层级表示（意味着无法预测整个图的标签），顾无法实现图分类任务。举个栗子，一个Graph，可以分成600个subgraph，每个节点都存在于其中的某个subgraph（一个节点只存在于一个subgraph中），每个subgraph拥有一个标签，如何预测subgraph的标签是这篇文章主要想解决的问题。传统的GNN的图分类方法都是为Graph中的所有节点生成Embedding，然后将对这些Embedding做全局聚合（池化），如简单的把属于同一个subgraph的节点求和或者输入到MLP中生成一个标签向量来表示整个subgraph，但是这样可能忽略的图的层级结构信息。 本文提出了一种端到端的可微可微图池化模块DiffPool，原理如下图所示： 在深度GNN中的每层中为节点学习可微的软簇分配，将节点映射到簇中，这些簇作为新的节点作为下一层GNN的输入。上图的Original Network部分是一个Subgraph，传统的方法是直接求出这个Subgraph中每个节点的Embedding，然后相加或输入到一个神经网络中，得到一个预测向量，这种方法可以称为“全局池化”。DiffPool中，假设第$l$层的输入是$1000$个簇（如果是第一层输入就是1000个节点），我们先设置第$l+1$层需要输入的簇的个数（假设为$100$），也就是第$l$层输出的簇个数，然后在$l$层中通过一个分配矩阵将$1000$个簇做合并，合并成100个“节点”，然后将这100个节点输入到$l+1$层中，最后图中的节点数逐渐减少，最后，图中的节点只有一个，这个节点的embedding就是整个图的表示，然后将图输入到一个多层感知机MLP中，得到预测向量，在于真值的one-hot向量做cross-entropy，得到Loss。 Model：DiffPool 一个Graph表示为$\mathcal{G} = (A,F)$，其中$A \in {0,1}^{n \times n}$是Graph的邻接矩阵，$F \in \mathbb{R}^{n \times d}$表示节点特征矩阵，每个节点有$d$维的特征。给定一个带标签的子图集$\mathcal{D}=\left\{\left(G_{1}, y_{1}\right),\left(G_{2}, y_{2}\right), \ldots\right\}$， 其中 $y_{i} \in \mathcal{Y}$表示每个子图$G_i \in \mathcal{G}$的标签，任务目标是寻找映射$f: \mathcal{G} \rightarrow \mathcal{Y}$，将图映射到标签集。我们需要一个过程来将每个子图转化为一个有限维度的向量$\mathbb{R}^D$。 Graph Neural Networks 一般，GNN可以表示成"Message Passing"框架： $$ H^{(k)}=M\left(A, H^{(k-1)} ; \theta^{(k)}\right) $$ 其中$H^{(k)} \in \mathbb{R}^{n \times d}$表示GNN迭代$k$次后的node embedding，$M$是一个Message扩散函数，由邻接矩阵$A$和一个可训练的参数$\theta^{(k)}$决定。$H^{(k-1)}$是由前一个message passing过程生成的node embedding。当$k = 1$时，第一个GNN的输入为$H^{(0)}$是原始的节点特征$H^{(0)} = F$。 GNN的一个主要目标是设计一个Message Passage函数$M$，GCN（kipf.2016）是一种流行的GNN，$M$的实现方式是将线性变换和ReLU非线性激活结合起来: $$ H^{(k)}=M\left(A, H^{(k-1)} ; W^{(k)}\right)=\operatorname{ReLU}\left(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(k-1)} W^{(k-1)}\right) $$ 其中，$\tilde{A} = A+I$是一个加上自环的邻接矩阵，$\tilde{D}=\sum_{j} \tilde{A}_{i j}$是$\tilde{A}$的度矩阵，$W^{(k)} \in \mathbb{R}^{d \times d}$是一个可训练的权重矩阵，$W$与节点个数以及每个节点的度无关，可以看做一个特征增强矩阵，用来规定GCN的输出维度。 ...

最近在看GNN/GCN的时候遇到谱聚类，学了下，做了些笔记。 本文主要参考了：[1] https://www.cnblogs.com/pinard/p/6221564.html#!comments Introduction 谱聚类是图论中的算法，主要思想是空间中距离较远的两个点之间边的权重值较低， 距离较近的两个点之间边的权重值较高， 通过对所有数据点组成的图（Graph）进行切图， 使不同子图之间边的权重和尽可能低， 子图内边的权重值的和尽可能高，从而达到聚类的目的。 基础1： 无向权重图 对于边$(v_i,v_j)$, 它的权重$w_{ij} > 0$。对于没有边的节点$v_i$和$v_j$, 他们之间的权重$w_{ij}=0$。图中的节点$v_i$, 它的度$d_i$定义为和它连接的所有边的权重之和，即： $$ d_i = \sum_{j=1}^n w_{ij} $$ 根据所有节点的度值，我们可以得到一个度矩阵$D$: $$ D=\displaystyle \left(\begin{array}{ccc}{d_{1}} & {\ldots} & {\ldots} \\\ {\ldots} & {d_{2}} & {\ldots} \\\ {\vdots} & {\vdots} & {\ddots} \\\ {\ldots} & {\ldots} & {d_{n}}\end{array}\right) ^{n\times n} $$ 是一个$n \times n$的对角阵，对角元素是每个节点的度和。 定义图的邻接矩阵为$W \in \mathbb{R}^{n \times n}$， 每个元素$W_{ij}$表示节点对$(v_i,v_j)$之间的权重。 对于$V$中的一个子节点集$A \subset V$， 定义： $$|A|=A 中的节点个数 $$ $$vol(A) = \sum_{i \in A} d_i \quad 表示A中所有节点的权重之和$$ ...

论文地址：M-NMF Introduction Network Embedding的基本需求是保存网络机构和固有属性。而先前的方法主要保存了网络的围观结构（microscopic structure）如一阶相似度和二阶相似度（LINE，SDNE等）， 忽略了网络结构的介观社区结构（mesoscopic community structure）。针对这个问题，本文提出了一种模块化非负矩阵分解模型M-NMF，该模型将网络的社区结构融入network embedding中。利用节点表示和社区结构之间的一致关系（consensus relationship）， 联合优化基于非负矩阵分解的表示学习模型和基于模块化的社区发现模型， 这样就可以在节点表示中同时保存了微观网络结构和介观社区结构。 具体来说，对于微观结构（节点对相似性），本文使用矩阵分解来融合节点的一节相似性和二阶相似性；对于介观社区结构，通过模块度约束项来检测社区。因此，上面的两项可以通过节点的表示和基于辅助社区表示矩阵社区结构之间的一致关系来联合优化。同时，本文给出了乘法更新策略，保证了再推导参数的时候的正确性和收敛性。 M-NMF Model 对于一个无向图$G=(V,E)$, 图中有$n$个节点和$e$条边，用一个0,1二值邻接矩阵表示为$\mathbf{A}=[A_{i,j}] \in \mathbb{R}^{n \times n}$。 $\mathbf{U} \in \mathbb{R}^{n \times m}$ 为节点的表示矩阵，其中$m \leq n$，$m$是节点的嵌入维度。 建模社区结构 本文采用基于模块最大化的社区发现方法 Modularity， 给定一个邻接矩阵表示的网络$\mathbf{A}$，$\mathbf{A}$包含两个社区，根据Newman 2006b，模块度可以定义如下： $$ Q=\frac{1}{4 e} \sum_{i j}\left(A_{i j}-\frac{k_{i} k_{j}}{2 e}\right) h_{i} h_{j} $$ 其中，$k_i$表示节点$i$的度，如果$i$在第一个社区中，那么$h_i=1$,否则$h_i = -1$。 $k_ik_j$表示将所有边一分为二 参考模块度Q，那么节点$i$,$j$之间可能产生的边数。$\frac{k_{i} k_{j}}{2 e}$如果所有边随机放置，节点$i$,$j$之间的期望边数。定义一个模块度矩阵$\mathbf{B} \in \mathbb{R}^{n \times n}$，其中$B_{i,j}=A_{i,j}-\frac{k_{i} k_{j}}{2 e}$，那么$Q=\frac{1}{4 e} \mathbf{h}^{T} \mathbf{B h}$，其中$\mathbf{h}=[h_i] \in \mathbb{R}^n$，表示社区成员指标器。 如果将$Q$拓展到$k > 2$个社区，那么： $$ Q=\operatorname{tr}\left(\mathbf{H}^{T} \mathbf{B H}\right), \quad \text { s.t. } \quad \operatorname{tr}\left(\mathbf{H}^{T} \mathbf{H}\right)=n $$ 其中$tr()$表示矩阵的迹（主对角线元素和），$\mathbf{H}$是社区成员指标器，$\mathbf{H} \in \mathbb{R}^{n \times k}$，每行表示一个节点所属社区的one-hot编码。 ...

文章链接：Embedding_IC Introduction 本文基于Network Embedding优化了传统的独立级联模型（IC），用以学习一个更具鲁棒性的扩散概率。 对于网络和社交数据，分析用户交互来为扩散现象建模具有以下困难： 用户通常是异质的，伴随着不同的行为或兴趣。并且他们通过各种通道同时交互。 用户之间的关系很难检测和表征。 例如，在信息传播过程中，不经常交互的用户之间的“弱关系”很重要，而它们很难被捕获。 不同应用中的级联长度变化很大，难以学习和预测。 本文的目的是通过从观察中学习来开发扩散模型。为此，本文专注于独立级联模型（IC），该模型定义了网络中的扩散迭代过程。在这种情况下，建模扩散的问题归结为__学习表征用户间隐含的相互影响关系的概率分布__，以便发现网络的主要通信通道。我们在此考虑的模型执行以下假设： 影响传播是二元的（被感染或不被感染）， 扩散网络未知， 影响关系不依赖于传播的内容， 用户之间的感染概率不会随时间变化（一旦分配了两个节点间的感染概率，那么该概率固定）。 本文基于NE，将扩散空间建模为一个连续的潜在空间，用户间的相对位置用于定义内容传输的可能性。用户靠的越近，传播概率越高。如下图所示： Model Notations 传播事件集$\mathcal{D}={D_1,D_2,…,D_n}$ 可以视为一个graph中的$n$个级联（cascade）。其中，一个传播事件$D$是一个带有时间戳的用户集。值得注意的是，级联中的用户并不知道是谁传染它，仅知道它何时被传染。 给定一个社交网络，有$N$个用户：$\mathcal{U}={u_1,u_2,…,u_N}$，一个传播级联$D$可以定义为user和它的timestamp的集合：$D = {(u,t^D(u)) | u \in \mathcal{U} \wedge t^D(u)< \infty}$， 其中，$t^D: \mathcal{U} \to \mathbb{R}^+$ 表示用户被传染的时间戳， $\infty$表示未被传染的用户。每个用户的时间戳$t^D$表示该用户相对于源用户（source user）被传染的时间，$t^D(source \quad user) = 0$。接下来，用$D(t)$表示在时间戳$t$之前被传染的用户：$D(t) = {u \in \mathcal{U} | t^D(u)<t}$。对称地，用$\bar{D}(t)$表示在时间戳$t$之前没有被感染的用户。 $D(\infty)$表示最终所有被感染的用户，$\bar{D}(infty)$表示最终所有没被感染的用户。 Diffusion Model 本文将级联embed到连续空间中，用以捕获扩散关系的规律性。本文只考虑传播的顺序，而不是确切的感染时间戳。 在Embedding_IC中，在一个传播事件(级联)$D$中，一个用户是否被感染的概率取决于先前所有已经被感染的节点。给定一个已经被影响的用户集$I \in \mathcal{U}$, $P(v|I)$表示给定活跃用户集$I$时，节点$v$被传染的概率，其中$v \in \mathcal{U} \backslash I$: $$ P(v|I) = 1-\prod_{u \in I}(1-P_{u,v}) $$ 上式中，$\prod_{u \in I}(1-P_{u,v})$表示$I$中所有节点都不影响$v$的概率。那么$P(v|I)$就可以表示$v$被感染的概率。 ...

影响力传播模型 社交网络上影响力最大化问题需要借助相应的影响力传播模型，影响力传播模型的选择 LC IT模型（独立级联模型和线性阈值模型） WC（权重级联模型） HD（热传播模型） SIR（传染病模型） MIA模型（路径相关） 投票模型 巴斯模型 影响力最大化算法 目前有的几个影响力最大化的算法 基于目标函数的子模性质的算法（一般是贪心算法和贪心算法的改进） A note on maximizing a submodular set function subject to a knapsack constraint 这个文章主要是把问题扩展了，认为选择每个节点是有不同的代价的，而不同于传统的问题，传统的问题中，每个节点的选择大家都是一样的，因此，在总代价一定的情况下，那么问题就是选择固定个数的节点即可，但是如果每个节点的选择代价不一样，在总代价一定的情况下，选择的节点的个数就不一样 Cost-effective outbreak detection in networks （CELF算法） Celf ++ : optimizing the greedy algorithm for influence maximization in social networks（CELF++算法） 这个文章就是大名鼎鼎的CELF算法，利用子模性质和边际效益递减对贪心算法进行优化，同理还有CELF++算法也是大致相同的思路 基于中心性的启发式算法 Efficient influence maximization in social networks W.Chen （DegreeDiscount算法） 这个算法也是启发式算法，主要在于，每当选择一个节点后，认为这个节点不会再被影响，因此，它的邻居节点地度-1 A potential-based node selection strategy for influence max- imization in a social network （TM算法） 这个算法也是一种启发式算法，它是以节点地潜在地影响力作为启发的因素去选择初始的节点，同时设置了一个参数c，分为两个阶段，第一个阶段启发式的选择潜在影响力最大的若干个节点，第二阶段用贪心算法对这些第一阶段选择的种子节点进行筛选，当参数c为0，也就是没有第一阶段，那么算法就变成了传统的贪心算法。算法的缺点也很明显，首先参数c的选择依赖于经验判断，其次是启发式，准确率没有保证，再次也需要使用贪心算法，因此时间复杂度很高 ...