zy123/md_files
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
md_files/科研/传统图机器学习.md

15 KiB
Raw Permalink Blame History

传统图机器学习和特征工程

节点层面的特征工程

目的：描述网络中节点的结构和位置

eg:输入某个节点的D维向量，输出该节点是某类的概率。

节点度 (Node Degree)

定义： 节点度是指一个节点直接连接到其他节点的边数。

  • 无向图中： 节点的度即为与其相邻的节点数。
  • 有向图中： 通常区分为入度（有多少条边指向该节点）和出度（从该节点发出的边的数量）。

意义： 节点度直观反映了节点在网络中的直接连接能力。度高的节点通常在信息传播或资源分配中具有较大作用。

例如，在社交网络中，一个拥有大量好友的用户（高节点度）可能被视为“热门”或者“活跃”的社交人物。

节点中心性 (Node Centrality)

定义： 节点中心性是一类衡量节点在整个网络中“重要性”或“影响力”的指标。其核心思想是，不仅要看节点的直接连接数，还要看它在网络中的位置和在信息流动中的角色。

常见的指标：

  • 介数中心性 (Betweenness Centrality)： 衡量节点位于其他节点间最短路径上的频率，反映其作为“桥梁”的作用。
  • 接近中心性 (Closeness Centrality)： 衡量节点到网络中其他节点平均距离的倒数，距离越近中心性越高。
  • 特征向量中心性 (Eigenvector Centrality)： 除了考虑连接数量外，还考虑邻居节点的“重要性”，连接到重要节点会提升自身的中心性。

举例：

假设有 3 个节点，记为 $1, 2, 3$，它们构成了一条链：


1 \; \leftrightarrow \; 2 \; \leftrightarrow \; 3

即只有边 (1,2) 和 $(2,3)$，没有直接连接 $(1,3)$。

令邻接矩阵 A 为：


A \;=\;
\begin{pmatrix}
0 & 1 & 0\\
1 & 0 & 1\\
0 & 1 & 0
\end{pmatrix}.

介数中心性（必经之地）：


\displaystyle
c_v \;=\; \sum_{s \neq t}\; \frac{\sigma_{st}(v)}{\sigma_{st}},

其中

  • \sigma_{st} 表示从节点 s 到节点 t 的所有最短路径数；
  • \sigma_{st}(v) 表示这些最短路径当中经过节点 $v$ 的条数；
  • 求和一般只考虑 s \neq t 且 s \neq v \neq t 的情形，避免把端点本身算作中间节点。

换言之，节点 v 的介数中心性就是它作为“中间节点”出现在多少对 (s,t) 的最短路径上。

对 3 个节点 ${1,2,3}$，不同的 (s,t) 有：

  1. $(s,t)=(1,2)$：最短路径为 $(1,2)$。

    • 路径上节点：1 → 2
    • 中间节点：无 (1、2 是端点)

  2. $(s,t)=(1,3)$：最短路径为 $(1,2,3)$。

    • 路径上节点：1 → 2 → 3
    • 中间节点：2

  3. $(s,t)=(2,3)$：最短路径为 $(2,3)$。

    • 路径上节点：2 → 3
    • 中间节点：无 (2、3 是端点)

  4. 节点 1

    • 只会出现在路径 (1,2) 或 (1,3) 的端点位置；(2,3) 的最短路径不包含 1。

    • 端点不计作中间节点，所以 \sigma_{st}(1) = 0 对所有 $s\neq t\neq 1$。

    • 因此

      
c_1 = 0.

  5. 节点 2

    • 在 (1,3) 的最短路径 (1,2,3) 中，2 是中间节点。此时 $\sigma_{1,3}(2) = 1$；

    • (1,2) 路径 (1,2) 中 2 是端点，(2,3) 路径 (2,3) 中 2 也是端点，因此不计入中间节点。

    • 所以

      
c_2 = \underbrace{\frac{\sigma_{1,3}(2)}{\sigma_{1,3}}}_{=1/1=1} \;=\; 1.

接近中心性（去哪儿都近）：


c_v \;=\; \frac{1}{\sum_{u \neq v} d(u,v)},

其中 d(u,v) 表示节点 u 与节点 v 的最短路径距离。

节点1：

  • 与节点 2 的距离：$d(1,2)=1$。
  • 与节点 3 的距离：$d(1,3)=2$（路径 1→2→3）。
  • 距离和：\;1 + 2 = 3.
  • 接近中心性：\; c_1 = \tfrac{1}{3} \approx 0.333.

其他两节点同理。

特征向量中心性

特征向量中心性要求我们求解


A\,\mathbf{x} = \lambda\,\mathbf{x},

并选取对应最大特征值 \lambda 的特征向量 \mathbf{x} 来代表每个节点的中心性。

记 $\mathbf{x} = (x_1,,x_2,,x_3)^T$
这里 x_1 是节点 1 的中心性值，x_2 是节点 2 的中心性值，x_3 是节点 3 的中心性值

  1. 方程 A\,\mathbf{x} = \lambda\,\mathbf{x} 具体展开

    
\begin{pmatrix}
0 & 1 & 0\\
1 & 0 & 1\\
0 & 1 & 0
\end{pmatrix}
\begin{pmatrix}
x_1\\
x_2\\
x_3
\end{pmatrix}
\;=\;
\lambda
\begin{pmatrix}
x_1\\
x_2\\
x_3
\end{pmatrix}.

    这意味着：

    
\begin{cases}
1.\; x_2 = \lambda\, x_1, \\
2.\; x_1 + x_3 = \lambda\, x_2, \\
3.\; x_2 = \lambda\, x_3.
\end{cases}

  2. 求解最大特征值 \lambda 及对应的 $\mathbf{x}$

    • 通过特征多项式可知本矩阵的最大特征值为 $\sqrt{2}$。

    • 最终（若需单位化）可以将向量归一化为

      
\mathbf{x} = \frac{1}{2}\,\begin{pmatrix} 1 \\ \sqrt{2} \\ 1 \end{pmatrix}.

  3. 解释

    • 节点 2 的得分最高（$\tfrac{\sqrt{2}}{2}\approx 0.707$），因为它连接了节点 1 和 3，两边的贡献都能“传递”到它。
    • 节点 1 和 3 的得分相同且略低（$\tfrac{1}{2}=0.5$），因为它们都只与节点 2 相连。

聚类系数 (Clustering Coefficient)

定义：
聚类系数描述一个节点的邻居之间彼此相连的紧密程度。

  • 对于某个节点，其局部聚类系数计算为： 
    
C = \frac{2 \times \text{实际邻居间的边数}}{k \times (k-1)}
    其中 k 为该节点的度数。

意义：

  • 高聚类系数： 表示节点的邻居往往彼此熟识，形成紧密的小团体。
  • 低聚类系数： 则说明邻居之间联系较少，节点更多处于桥梁位置，可能连接不同的社群。

在很多网络中，聚类系数能揭示局部社区结构和节点的协同效应。

Graphlets

定义：
Graphlets 是指网络中规模较小（通常由3至5个节点构成）的非同构子图。

  • 通过统计一个节点参与的各种 graphlet 模式的数量，我们可以构造出该节点的 Graphlet Degree Vector (GDV)。

意义：

  • Graphlets 能捕捉节点在局部网络结构中的精细模式，比单纯的度数或聚类系数提供更丰富的信息。
  • 在很多应用中（如生物网络分析或社交网络挖掘），通过分析节点参与的 graphlet 模式，可以更好地理解节点的功能和在整个网络中的角色。

Graphlets 被视为网络的“结构指纹”，有助于区分功能不同的节点。

连接层面的特征工程

目的：通过已知连接补全未知连接

eg: AB之间有连接，BC之间有连接，那么AC之间是否可能有连接呢？

法一：直接提取连接的特征，把连接变成D维向量(推荐)。

法二：把连接两端节点的D维向量拼接，即上一讲的节点特征拼接（不推荐，损失了连接本身的结构信息。）

Distance-based Feature

核心思路： 用两个节点之间的最短路径长度（或加权距离等）作为边的特征，衡量节点对的“接近”程度。

Local Neighborhood Overlap

核心思路： 度量两个节点在其“一阶邻居”层面共享多少共同邻居，或者它们的邻居集合相似度如何。

  1. Common Neighbors

    
\text{CN}(u,v) \;=\; \bigl|\,N(u)\,\cap\,N(v)\bigr|,

    其中 N(u) 是节点 u 的邻居集合，\cap 表示交集。数值越大，表示两节点在局部网络中有更多共同邻居。

  2. Jaccard Coefficient

    
\text{Jaccard}(u,v) \;=\; \frac{\bigl|\,N(u)\,\cap\,N(v)\bigr|}{\bigl|\,N(u)\,\cup\,N(v)\bigr|}.

    反映了两个节点邻居集合的交并比，越大则两者邻居越相似。

  3. Adamic-Adar

    
\text{AA}(u,v) \;=\; \sum_{w \,\in\, N(u)\,\cap\,N(v)} \frac{1}{\log\,\bigl|N(w)\bigr|}.

    共同邻居数目较多、且这些邻居本身度数越小，贡献越大。常用于社交网络链接预测。（直观理解：如果AB都认识C，且C是个社牛，那么AB之间的友谊就不一定好）

Global Neighborhood Overlap

核心思路： 不只看“一阶邻居”，还考虑更大范围（如 2 步、3 步乃至更多跳数）上的共同可达节点，或更广泛的结构相似度。

Katz 指标：累加节点间所有长度的路径并衰减；

Random Walk：基于随机游走来度量节点对的全局可达性；

Graph Embedding：DeepWalk、node2vec等，都可将多跳结构信息编码到向量表示里，再用向量相似度当作边特征。

真实情况如何编码边的特征？

在一个 边的特征工程 任务中，可以将 Distance-based Feature、Local Neighborhood Overlap 和 Global Neighborhood Overlap 等特征组合起来，形成一个完整的特征向量。

例如：对于每条边 $ (u,v) $，我们提取以下 6 种特征：

  1. 最短路径长度 d(u,v) (Distance-based Feature)
  2. 共同邻居数 CN(u,v) (Local Neighborhood Overlap)
  3. Jaccard 系数 Jaccard(u,v) (Local Neighborhood Overlap)
  4. Adamic-Adar 指标 AA(u,v) (Local Neighborhood Overlap)
  5. Katz 指数 Katz(u,v) (Global Neighborhood Overlap)
  6. Random Walk 访问概率 RW(u,v) (Global Neighborhood Overlap)

对于图中某条边 $ (A, B) $，它的特征向量可能是：


\mathbf{f}(A, B) = \big[ 2, 5, 0.42, 0.83, 0.31, 0.45 \big]

图层面的特征工程

目的：网络相似度、图分类（已知分子结构判断是否有xx特性）

当我们要对整张图进行分类或比较（如图分类、图相似度计算等），需要将图转化为可比较的向量或特征。最朴素的想法是：

​ Bag-of-Node-Degrees：统计每个节点的度，然后构建一个“度分布”或“度直方图”。

  • 例如，对图 $G$，我们计算 $\phi(G) = [,\text{count of deg}=1,\ \text{count of deg}=2,\ \dots,]$。
  • 缺点：只关注了节点度，无法区分很多结构不同、但度分布相同的图。

为解决这个不足，人们提出了更精细的“Bag-of-*”方法，把节点周围的更丰富结构（子图、子树、图形）纳入统计，从而形成更有判别力的特征。

Graphlet Kernel

  • Graphlets：指小规模（如 3 节点、4 节点、5 节点）的非同构子图。
  • 做法：枚举或随机采样网络中的所有小型子图（graphlets），并根据其类型计数出现频率。
    • 比如在 4 节点层面，有 6 种不同的非同构结构，就统计每种结构出现多少次。
  • 得到的特征：一个“graphlet type”直方图，即 $\phi(G) = \big[\text{count}(\text{graphlet}_1), \dots, \text{count}(\text{graphlet}_k)\big]$。
  • 优点：比单纯节点度更能捕捉网络的局部模式。
  • 缺点：当图很大时，遍历或采样 graphlet 代价较高；仅依赖小子图也可能忽略更大范围结构。

Weisfeiler–Lehman Kernel

  • Weisfeiler–Lehman (WL) 核是一种基于迭代标签传播的方法，用于图同构测试和图相似度计算。
  • 核心思路：
    1. 初始标签：给每个节点一个初始标签（可能是节点的类型或颜色）。
    2. 迭代更新：在每一步迭代中，将节点自身标签与其邻居标签拼接后做哈希，得到新的标签。
    3. 记录“标签多重集”：每次迭代会产生新的节点标签集合，可视为“节点子树结构”的某种编码。
  • Bag-of-Labels / Bag-of-Subtrees：
    • 在每一轮迭代后，统计各类标签出现次数，累加到特征向量中。
    • 相当于对节点子树或“局部邻域结构”做词袋统计。
  • 优点：在保留更多结构信息的同时，计算复杂度相对可控。
  • 缺点：仍然可能有一定的“同构测试”盲区；对于非常复杂的图，标签碰撞可能出现。

例子：

假设我们有一个简单的无向图，包含 4 个节点和 4 条边，结构如下：

1 — 2 — 3
    |
    4

1. 初始化标签

首先，给每个节点一个初始标签。假设我们直接用节点的度数作为初始标签：

初始标签如下：

  • 节点 1: 1
  • 节点 2: 3
  • 节点 3: 1
  • 节点 4: 1

2. 第一次迭代

在第一次迭代中，每个节点的标签会更新为其自身标签和邻居标签的拼接，然后通过哈希函数生成新的标签。

  • 节点 1：

    • 邻居是节点 2，标签为 3。
    • 拼接后的标签为 (1, 3)。
    • 假设哈希结果为 A。

  • 节点 2：

    • 邻居是节点 1、3、4，标签分别为 1、1、1。
    • 拼接后的标签为 (3, 1, 1, 1)。
    • 假设哈希结果为 B。

  • 节点 3：

    • 邻居是节点 2，标签为 3。
    • 拼接后的标签为 (1, 3)。
    • 假设哈希结果为 A。

  • 节点 4：

    • 邻居是节点 2，标签为 3。
    • 拼接后的标签为 (1, 3)。
    • 假设哈希结果为 A。

第一次迭代后的标签如下：

  • 节点 1: A
  • 节点 2: B
  • 节点 3: A
  • 节点 4: A

3. 第二次迭代

  • 节点 1：

    • 邻居是节点 2，标签为 B。
    • 拼接后的标签为 (A, B)。
    • 假设哈希结果为 C。

  • 节点 2：

    • 邻居是节点 1、3、4，标签分别为 A、A、A。
    • 拼接后的标签为 (B, A, A, A)。
    • 假设哈希结果为 D。

  • 节点 3：

    • 邻居是节点 2，标签为 B。
    • 拼接后的标签为 (A, B)。
    • 假设哈希结果为 C。

  • 节点 4：

    • 邻居是节点 2，标签为 B。
    • 拼接后的标签为 (A, B)。
    • 假设哈希结果为 C。

第二次迭代后的标签如下：

  • 节点 1: C
  • 节点 2: D
  • 节点 3: C
  • 节点 4: C

4. 停止条件

通常，WL Kernel 会进行多次迭代，直到节点的标签不再变化（即收敛）。在这个例子中，假设我们只进行两次迭代。

5.统计标签的多重集

在每次迭代后，统计图中所有节点的标签分布（即“标签多重集”），并将其作为图的特征。

  • 初始标签多重集：

    • 标签 1 出现 3 次（节点 1、3、4）。
    • 标签 3 出现 1 次（节点 2）。

  • 第一次迭代后的标签多重集：

    • 标签 A 出现 3 次（节点 1、3、4）。
    • 标签 B 出现 1 次（节点 2）。

  • 第二次迭代后的标签多重集：

    • 标签 C 出现 3 次（节点 1、3、4）。
    • 标签 D 出现 1 次（节点 2）。

\phi(G) = [\text{count}(1), \text{count}(3), \text{count}(A), \text{count}(B), \text{count}(C), \text{count}(D)].  \\
\phi(G) = [3, 1, 3, 1, 3, 1].

直观理解

  • 初始标签：只关注节点的度数。
  • 第一次迭代：关注节点的度数及其邻居的度数。
  • 第二次迭代：关注节点的度数、邻居的度数，以及邻居的邻居的度数。
  • 随着迭代的进行，WL Kernel 能够捕捉到越来越复杂的局部结构信息。