提出非耗散图传播方法,解决异质图社区发现难题
Non-Dissipative Graph Propagation for Non-Local Community Detection
- 用反对称权重矩阵构建非耗散动力系统,实现长程信息传播
- 在10个数据集上优于传统方法,尤其在高/中度异质图中表现突出
- 适合处理节点远距离关联的复杂网络社区发现任务
图上的社区检测旨在将节点聚类为有意义的组,但在异质图中尤为困难——相似节点和同社区成员往往相距遥远。这在基于图神经网络的方法中尤为明显,因其依赖固有的局部消息传递机制来学习节点表示。本文认为,消息传递中传播长程信息的能力是有效解决异质图社区检测的关键。为此,我们提出无监督反对称图神经网络(uAGNN),利用非耗散动力系统确保稳定性并高效传播长程信息。通过采用反对称权重矩阵,uAGNN同时捕捉局部与全局图结构,克服了异质场景的限制。在十个数据集上的实验表明,uAGNN在高和中度异质设置下显著优于传统方法,而后者无法利用长程依赖。这些结果凸显了uAGNN在多样化图环境中作为强大无监督社区检测工具的潜力。
原文摘要 · Abstract (English)
Community detection in graphs aims to cluster nodes into meaningful groups, a task particularly challenging in heterophilic graphs, where nodes sharing similarities and membership to the same community are typically distantly connected. This is particularly evident when this task is tackled by graph neural networks, since they rely on an inherently local message passing scheme to learn the node representations that serve to cluster nodes into communities. In this work, we argue that the ability to propagate long-range information during message passing is key to effectively perform community detection in heterophilic graphs. To this end, we introduce the Unsupervised Antisymmetric Graph Neural Network (uAGNN), a novel unsupervised community detection approach leveraging non-dissipative dynamical systems to ensure stability and to propagate long-range information effectively. By employing antisymmetric weight matrices, uAGNN captures both local and global graph structures, overcoming the limitations posed by heterophilic scenarios. Extensive experiments across ten datasets demonstrate uAGNN's superior performance in high and medium heterophilic settings, where traditional methods fail to exploit long-range dependencies. These results highlight uAGNN's potential as a powerful tool for unsupervised community detection in diverse graph environments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。