2025-11-20T02:28:14.687819

Heterogeneous Attributed Graph Learning via Neighborhood-Aware Star Kernels

Huang, Yao, Chen et al.

Attributed graphs, typically characterized by irregular topologies and a mix of numerical and categorical attributes, are ubiquitous in diverse domains such as social networks, bioinformatics, and cheminformatics. While graph kernels provide a principled framework for measuring graph similarity, existing kernel methods often struggle to simultaneously capture heterogeneous attribute semantics and neighborhood information in attributed graphs. In this work, we propose the Neighborhood-Aware Star Kernel (NASK), a novel graph kernel designed for attributed graph learning. NASK leverages an exponential transformation of the Gower similarity coefficient to jointly model numerical and categorical features efficiently, and employs star substructures enhanced by Weisfeiler-Lehman iterations to integrate multi-scale neighborhood structural information. We theoretically prove that NASK is positive definite, ensuring compatibility with kernel-based learning frameworks such as SVMs. Extensive experiments are conducted on eleven attributed and four large-scale real-world graph benchmarks. The results demonstrate that NASK consistently achieves superior performance over sixteen state-of-the-art baselines, including nine graph kernels and seven Graph Neural Networks.

academic

Heterogeneous Attributed Graph Learning via Neighborhood-Aware Star Kernels

基本信息

论文ID: 2511.11245
标题: Heterogeneous Attributed Graph Learning via Neighborhood-Aware Star Kernels
作者: Hong Huang, Haiming Chen, Hang Gao, Chengyu Yao
机构: Institute of Software, Chinese Academy of Sciences
分类: cs.LG (Machine Learning)
发表时间: 2025年11月14日 (arXiv preprint)
论文链接: https://arxiv.org/abs/2511.11245

摘要

属性图（attributed graphs）广泛存在于社交网络、生物信息学和化学信息学等领域，通常具有不规则拓扑结构以及数值型和类别型混合属性。虽然图核方法为图相似性度量提供了理论框架，但现有核方法难以同时捕获异构属性语义和邻域信息。本文提出邻域感知星核（NASK），一种新颖的图核方法。NASK利用Gower相似系数的指数变换来高效建模数值和类别特征，并采用经Weisfeiler-Lehman迭代增强的星子结构来整合多尺度邻域结构信息。理论证明NASK是正定的，确保与SVM等核学习框架的兼容性。在11个属性图和4个大规模真实图基准上的广泛实验表明，NASK在16个最先进基线（包括9个图核和7个图神经网络）上持续取得优越性能。

研究背景与动机

1. 要解决的核心问题

属性图学习面临两个核心挑战：

异构属性建模：图节点和边同时包含数值型和类别型属性，现有方法难以统一处理
结构信息捕获：需要有效整合局部邻域结构信息和多跳依赖关系

2. 问题的重要性

属性图在多个关键领域有广泛应用：

化学信息学：分子结构表示（原子类型为类别属性，化学性质为数值属性）
生物信息学：蛋白质结构分析
社交网络：用户画像和关系建模

3. 现有方法的局限性

图核方法的不足：

离散化方法（如Hash Graph Kernel）会损失原始属性语义
基于分布的方法（如WWL）缺乏正定性的形式化保证
直接组合方法（加权求和）会导致语义信息丢失

图神经网络的局限：

表达能力理论上不超过1-WL测试
在小样本场景下稳定性较差
可解释性不足

4. 研究动机

本文旨在设计一个同时满足以下要求的图核方法：

统一的异构属性处理：避免离散化带来的信息损失
丰富的结构表达：超越固定子结构的局限
理论保证：证明正定性以确保学习算法的收敛性
计算效率：在大规模图上保持可扩展性

核心贡献

提出NASK核方法：首个同时有效处理异构属性和邻域结构信息的正定图核
设计正定属性相似函数：基于Gower相似系数的指数变换，理论证明其正定性，统一建模数值和类别特征
星子结构与WL迭代融合：利用星图作为局部结构单元，通过WL算法扩展实现多跳邻域信息聚合
完整理论分析：形式化证明NASK及其所有组件的正定性，确保诱导有效的再生核希尔伯特空间（RKHS）
广泛实验验证：在15个基准数据集上超越16个强基线，包括传统图核和GNN方法，准确率提升最高达10.2%

方法详解

任务定义

输入：属性图集合 $\mathcal{G} = \{G_1, G_2, ..., G_N\}$ ，其中每个图 $G = \langle A, V, E, \lambda, F \rangle$

$V$ : 节点集合
$E$ : 边集合
$A$ : 属性名称集合
$F$ : 属性值集合（包含数值和类别值）
$\lambda: A \times (V \cup E) \rightarrow F$ : 属性映射函数

输出：图之间的核矩阵 $K \in \mathbb{R}^{N \times N}$ ，其中 $K_{ij} = K_{NAS}(G_i, G_j)$

目标：设计正定核函数用于图分类任务（通过SVM）

模型架构

NASK采用三层递进式设计：

层次1：属性相似度函数P

对于单个属性维度 $d$ ，首先定义Gower相似度：

数值属性： $s_d(x_d, x'_d) = 1 - \frac{|x_d - x'_d|}{\text{range}_d}$

类别属性： $s_d(x_d, x'_d) = \begin{cases} 1, & \text{if } x_d = x'_d \\ 0, & \text{otherwise} \end{cases}$

然后应用指数变换得到正定核： $s'_d(x_d, x'_d) = \exp(-\gamma(1 - s_d(x_d, x'_d)))$

多维属性相似度： $P(v, v') = \frac{1}{D} \sum_{d=1}^{D} s'_d(\lambda(A,v)_d, \lambda'(A',v')_d)$

关键创新：通过证明 $f_d(x_d, x'_d) = 1 - s_d(x_d, x'_d)$ 是条件负定（CND）函数，利用Berg等人的经典结果，保证指数变换后的正定性。

层次2：星子图核 $k_s$

星子图定义： $S = \langle A, V, E, \lambda, F, C, L \rangle$

$C$ : 中心节点
$L$ : 叶节点集合（中心节点的所有邻居）

星子图提取： $\mathcal{F}(v, G) = \langle G.A, \{v\} \cup N(v), \{(v,u) \in E | u \in N(v)\}, G.\lambda, G.F, v, N(v) \rangle$

星子图核： $k_s(S, S') = \sum_{n \in R^{-1}(S)} \sum_{n' \in R^{-1}(S')} P(C, C') \cdot P(n, n')$

其中 $R^{-1}(S)$ 是星图的有效分解（节点和边）， $P(C, C')$ 项强调中心节点相似度的重要性。

层次3：邻域感知星核 $K_{NAS}^{(H)}$

WL迭代扩展： $\mathcal{L}: S^{h-1} \times G \rightarrow S^h$

初始： $\hat{S}^{(1)}(G) = \{\mathcal{F}(v, G) | v \in V\}$

递归： $\hat{S}^{(h)}(G) = \{\mathcal{L}(S^{(h-1)}, G) | S^{(h-1)} \in \hat{S}^{(h-1)}(G)\}$

最终核定义： $K_{NAS}^{(H)}(G, G') = \sum_{h=1}^{H} \sum_{S \in \hat{S}^{(h)}(G)} \sum_{S' \in \hat{S}^{(h)}(G')} k_s(S, S')$

当 $H=1$ 时退化为基础星核 $K_S$ ；随着 $H$ 增加，捕获更高阶结构交互。

技术创新点

1. 统一的异构属性处理

与One-Hot编码对比：避免维度爆炸和稀疏性问题
与欧氏距离对比：对数值属性归一化，对类别属性提供有意义的相似度
优势：保持计算效率的同时保留原始语义

2. 星子结构的合理性

普遍性：真实图中普遍存在
语义性：捕获节点的局部邻域模式
效率性：线性时间复杂度 $O(|V|)$ 提取所有星图
与随机游走对比：固定中心表示提供更稳定的语义关系

3. WL迭代的必要性

克服固定子结构的局限
逐步聚合多跳邻域信息
理论上增强表达能力（接近k-WL测试）
消融实验显示移除WL导致3.5%-6.7%性能下降

4. 理论保证的完整性

完整的正定性证明链：

Lemma 1: $f_d$ 是CND
Lemma 2: $s'_d$ 是正定
Theorem 1: $P$ 是正定
Theorem 2: $k_s$ 是正定
Theorem 3: $K_S$ 是正定
Theorem 4: $K_{NAS}^{(H)}$ 是正定

复杂度分析

最坏情况时间复杂度： $O(Hn^2(n+m)^2d)$

$H$ : WL迭代深度
$n, m$ : 节点和边数量
$d$ : 属性维度

实际运行中通过核心相似度阈值剪枝显著加速。

实验设置

数据集

类别属性图（5个）：

MUTAG (188图，分子致突变性)
NCI1 (4,110图，化合物活性)
PTC_MR (344图，致癌性)
D&D (1,178图，蛋白质结构)
PROTEINS (1,113图，蛋白质功能)

数值属性图（2个）：

SYNTHETIC (4,337图，合成分子)
SYNTHIE (400图，4类合成数据)

异构属性图（4个）：

ENZYMES (600图，酶分类，18维数值+类别属性)
PROTEINS_full (1,113图，混合属性)
BZR (405图，药物分子)
COX2 (467图，药物分子)

大规模真实图（4个）：

Pubmed (引用网络，TF-IDF特征)
Cora (2,708论文，1,433维)
Citeseer (3,327论文，3,703维)
Pokec (社交网络，用户属性)

评价指标

分类准确率：10折交叉验证重复10次（共100次运行）
报告形式：均值 ± 标准差
统计显著性：通过多次运行保证

对比方法

图核方法（9个）：

WL-VH, PK, GH, ML：早期方法
HGK-WL：哈希加速
WWL：Wasserstein距离
RetGK：返回概率
RWK：正则化随机游走
SWWL：切片Wasserstein

图神经网络（7个）：

GCN, GraphSAGE, GIN：经典架构
GAT：注意力机制
KerGNN, AKGNN, KAGNN：核增强GNN

实现细节

NASK配置：

$\gamma$ ：通过验证集选择
WL深度 $H$ ：默认4（通过敏感性分析确定）
SVM参数 $C$ ：从 $\{10^{-3}, ..., 10^3\}$ 网格搜索

GNN配置：

2层架构，每层64隐藏单元
ReLU激活，全局求和池化
学习率：{0.001, 0.005, 0.01}
早停：patience=10

硬件环境：

GPU：NVIDIA RTX 4090
所有方法在相同硬件上评估

实验结果

主要结果

数值和异构属性图（表1）

数据集	最佳基线	NASK	提升
SYNTHETIC	RetGK: 96.2%	97.9%	+1.7%
SYNTHIE	WWL: 96.0%	97.1%	+1.1%
ENZYMES	RWK: 76.4%	78.3%	+1.9%
PROTEINS_full	RWK: 79.3%	81.1%	+1.8%
BZR	RWK: 86.2%	88.8%	+2.6%
COX2	RWK: 81.2%	82.9%	+1.7%

关键发现：

在所有6个数据集上达到SOTA
相比最佳图核平均提升2.0%
显著超越GNN方法（如GIN在ENZYMES上仅59.6%）

类别属性图（表2）

数据集	最佳基线	NASK	提升
MUTAG	RWK: 93.6%	95.9%	+2.3%
NCI1	WL-VH: 85.2%	88.0%	+2.8%
PTC_MR	KerGNN: 70.5%	76.7%	+6.2%
D&D	RetGK: 81.6%	82.1%	+0.5%
PROTEINS	RetGK: 75.8%	82.6%	+6.8%

关键发现：

PTC_MR上提升最显著（+6.2%），显示对复杂分子结构的强建模能力
在PROTEINS上相比GNN提升9.5%（vs GCN 63.1%）

大规模真实图（表3）

数据集	最佳基线	NASK	提升
Pubmed	KernelGCN: 87.84%	89.53%	+1.69%
Cora	KernelGCN: 88.40%	89.24%	+0.84%
Citeseer	KernelGCN: 80.28%	80.78%	+0.50%
Pokec	KAGNN: 81.07%	83.05%	+1.98%

关键发现：

在所有大规模数据集上保持最优
证明可扩展性和实用性

消融实验

组件贡献分析（表4，MUTAG/PTC_MR/PROTEINS_full/BZR）：

变体	平均准确率下降
w/ Random Walk	-6.7%
w/ One-Hot	-4.5%
w/ Euclidean	-3.8%
w/o WL Iteration	-5.0%

详细分析：

星子结构的重要性：
- 替换为随机游走导致D&D下降21.5%
- 固定中心表示捕获更丰富的语义关系
属性相似函数P的优势：
- 在PROTEINS_full上比One-Hot高3.7%
- 比欧氏距离高2.2%
- 统一处理混合属性的能力关键
WL迭代的必要性：
- 移除导致3.5%-6.7%下降
- 多跳邻域信息对复杂结构建模至关重要

WL深度敏感性分析

准确率趋势（图2a）：

NASK-1到NASK-4：准确率持续提升
NCI1: 85.0% → 88.0% (+3.0%)
PROTEINS: 79.8% → 82.5% (+2.7%)
NASK-5：部分数据集出现过拟合

运行时间（图2b）：

NASK-4到NASK-5：运行时间显著增加
NCI1: +28.7%
PROTEINS: +41.8%

最佳配置：NASK-4在准确率和效率间达到最佳平衡

案例分析

NCI1分子图可视化（图3）：

展示k=1到k=4跳星子图扩展
k=1：捕获直接化学环境（简单官能团）
k增加：捕获更大子结构和关系依赖
验证星子图提取设计的有效性

类概率热图（图6）：

强垂直条带：模型对类别分配高置信度
误分类样本稀少且集中
显示判别能力和预测一致性

鲁棒性分析

属性扰动实验（图5）：

高斯噪声：

BZR: 准确率保持>86%（噪声30%）
COX2: 保持>77%
中位数准确率稳定

特征掩码：

性能下降更显著但仍保持竞争力
窄四分位距显示稳定性

结论：NASK对连续扰动的容忍度优于离散信息丢失

运行时间对比

效率验证（表6）：

MUTAG: 0.61s (vs ML 8h+)
NCI1: 12m (vs GH 3.7h)
PROTEINS_full: 59s (vs ML 2.8h)

关键优势：

相比GH和ML快几个数量级
与轻量级方法（PK, RetGK）竞争
在中大规模数据集上更优

结论与讨论

主要结论

方法有效性：NASK在15个基准上全面超越16个强基线，平均提升2-6%
理论完备性：完整证明正定性，保证诱导有效RKHS，确保SVM等学习算法的收敛性和泛化能力
统一建模能力：成功解决异构属性和结构信息的联合建模难题
实用性：在大规模真实图上保持竞争力，运行时间可接受

局限性

计算复杂度：
- 最坏情况 $O(Hn^2(n+m)^2d)$
- 虽有剪枝优化，但在超大规模图（百万节点）上仍可能受限
超参数敏感性：
- $\gamma$ 参数需要验证集调优
- WL深度 $H$ 的选择需要权衡准确率和效率
假设条件：
- 假设属性范围已知（用于归一化）
- 对缺失属性的处理未详细讨论
表达能力边界：
- 虽超越1-WL，但仍受k-WL限制
- 对某些高阶图同构问题可能无法区分

未来方向

近似算法：
- 采样策略减少星子图对数量
- 低秩近似加速核矩阵计算
深度学习融合：
- 将NASK作为GNN的注意力机制
- 端到端学习核参数
动态图扩展：
- 处理时序属性图
- 增量更新核矩阵
多任务学习：
- 节点分类和链接预测
- 图生成任务

深度评价

优点

1. 理论严谨性（★★★★★）

完整的正定性证明链（6个定理/引理）
利用CND函数和Berg定理的经典结果
形式化保证学习算法的收敛性
这在图核领域相对罕见，多数方法缺乏理论保证

2. 方法创新性（★★★★★）

属性建模：首次将Gower系数的指数变换用于图核，兼顾效率和表达力
结构建模：星子结构+WL迭代的组合新颖，平衡局部和全局信息
统一框架：无缝整合异构属性和结构，避免信息损失

3. 实验充分性（★★★★★）

数据集多样性：15个数据集覆盖类别/数值/异构属性
基线全面性：16个强基线（9图核+7GNN）
消融完整性：系统分析每个组件的贡献
鲁棒性验证：噪声扰动实验
可视化分析：案例研究增强可解释性

4. 写作清晰度（★★★★☆）

逐层递进的方法描述
详细的数学推导和证明（附录）
丰富的图表辅助理解
小瑕疵：部分符号在首次使用前未定义

5. 实用价值（★★★★☆）

代码实现相对简单（基于已有库）
运行时间在可接受范围
适用于多个实际领域（化学、生物、社交网络）

不足

1. 可扩展性限制（★★★☆☆）

虽然在中等规模图上表现良好，但对百万节点级图的适用性未验证
核矩阵存储 $O(N^2)$ 在大数据集上可能成为瓶颈
建议：提供近似算法或分布式实现

2. 实验设置细节（★★★☆☆）

部分基线的超参数选择未详细说明
GNN的训练epoch较少（最多100），可能未充分收敛
缺少统计显著性检验（如t-test）

3. 对比分析深度（★★★☆☆）

与WWL等分布式方法的理论对比不够深入
为何正定性保证在实践中重要？缺少失败案例分析
建议：展示非正定核导致SVM失败的例子

4. 泛化能力讨论（★★★☆☆）

在合成数据集上的表现未单独分析
跨领域泛化能力（如从化学到社交网络）未评估
小样本学习场景未探讨

5. 计算优化空间（★★★☆☆）

核矩阵计算的并行化策略未讨论
GPU加速的潜力未充分挖掘
剪枝策略的具体实现细节不足

影响力评估

对领域的贡献（★★★★★）

理论贡献：为图核的正定性提供新范式
方法贡献：异构属性建模的统一解决方案
实证贡献：在多个基准上建立新SOTA

实用价值（★★★★☆）

化学信息学：分子性质预测的有效工具
生物信息学：蛋白质功能分类
局限：需要一定的核方法背景知识

可复现性（★★★★☆）

优点：
- 方法描述详细
- 数学公式完整
- 数据集公开可用
不足：
- 代码未开源（截至论文发表）
- 部分实现细节（如剪枝阈值）未明确

启发性（★★★★★）

后续工作方向：
- 核方法与深度学习的融合
- 动态图和时序图的扩展
- 其他领域的应用（如推荐系统）

适用场景

强烈推荐场景

小样本图分类：训练数据有限时，核方法比GNN更稳定
异构属性图：同时包含数值和类别属性
可解释性要求高：需要理解模型决策依据
理论保证需求：如安全关键应用

适用场景

中等规模图：节点数<10,000
静态图：结构和属性不随时间变化
监督学习：有标签数据可用

不推荐场景

超大规模图：百万节点级，计算成本过高
无属性图：纯结构信息，WL核等方法更简单
实时预测：核矩阵计算延迟较高
无监督学习：方法设计面向监督分类

综合评分

维度	评分	说明
创新性	9/10	方法设计新颖，理论严谨
严谨性	9/10	完整证明，实验充分
实用性	7/10	适用场景明确，但可扩展性受限
写作质量	8/10	结构清晰，细节丰富
影响力	8/10	对图核领域有重要贡献
总分	8.2/10	优秀论文

参考文献（精选）

Haussler (1999): Convolution kernels on discrete structures - R-convolution理论基础
Berg et al. (1984): Harmonic Analysis on Semigroups - CND函数与正定核的经典结果
Gower (1971): A general coefficient of similarity - Gower相似系数原始论文
Leman & Weisfeiler (1968): WL算法原始论文
Togninalli et al. (2019): WWL kernel - 主要竞争方法
Morris et al. (2023): Weisfeiler and Leman go machine learning - WL方法综述

总结

NASK是一篇理论与实践结合出色的图核方法论文。其核心贡献在于通过严格的数学证明，提供了首个同时处理异构属性和结构信息的正定图核。实验结果令人信服，在多个基准上建立了新的SOTA。尽管在超大规模图上的可扩展性仍有提升空间，但该方法为图核研究提供了新的范式，特别是在需要理论保证和可解释性的应用场景中具有重要价值。推荐给从事图机器学习、核方法和结构化数据分析的研究者阅读。