Differentiable Tripartite Modularity for Clustering Heterogeneous Graphs
This work addresses the challenge of clustering higher-order relational data, which is incremental as it extends existing differentiable modularity methods from homogeneous and bipartite to tripartite graphs.
The paper tackled the problem of clustering heterogeneous graphs with three node types by introducing a differentiable tripartite modularity formulation, which enabled end-to-end community detection with linear complexity and demonstrated robust convergence on urban cadastral data.
Clustering heterogeneous relational data remains a central challenge in graph learning, particularly when interactions involve more than two types of entities. While differentiable modularity objectives such as DMoN have enabled end-to-end community detection on homogeneous and bipartite graphs, extending these approaches to higher-order relational structures remains non-trivial. In this work, we introduce a differentiable formulation of tripartite modularity for graphs composed of three node types connected through mediated interactions. Community structure is defined in terms of weighted co-paths across the tripartite graph, together with an exact factorized computation that avoids the explicit construction of dense third-order tensors. A structural normalization at pivot nodes is introduced to control extreme degree heterogeneity and ensure stable optimization. The resulting objective can be optimized jointly with a graph neural network in an end-to-end manner, while retaining linear complexity in the number of edges. We validate the proposed framework on large-scale urban cadastral data, where it exhibits robust convergence behavior and produces spatially coherent partitions. These results highlight differentiable tripartite modularity as a generic methodological building block for unsupervised clustering of heterogeneous graphs.