Differentiable Tripartite Modularity for Clustering Heterogeneous Graphs
Benoît Hurpeau · 2026
Read Differentiable Tripartite Modularity for Clustering Heterogeneous Graphs by Benoît Hurpeau (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-09864.txt.
Introduction
Grouping mixed linked data stays a challenge in graph learning, most when links involve more than two types. Benoît Hurpeau notes smooth modular goals such as DMoN enabled end-to-end group finding on even and two-part graphs, yet spreading these ways to higher linked forms stays hard. His 2026 paper offers a smooth form of three-part modular for graphs of three node types linked through go-between links.
Group structure is defined through weighted co-paths across the three-part graph, with factored math skipping open build of third-order tensors. Shape scaling at pivot nodes controls degree mix and ensures tuning. The final goal tunes with a graph neural network end-to-end while keeping cost in edges. Tests on large urban land data show settling and in-space tidy splits, setting smooth three-part modular as a block for free grouping of mixed graphs.
Catalog record
| CREATOR | Benoît Hurpeau |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-09864
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Differentiable Tripartite Modularity for Clustering Heterogeneous Graphs Benoît Hurpeau Abstract 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. 1 Introduction Modularity-based objectives have long provided an interpretable criterion for community detection, by comparing observed connectivity patterns to a suitable null model [ 10 , 5 ] . Recent advances have introduced differentiable relaxations of modularity, such as DMoN, enabling end-to-end optimization jointly with graph neural network encoders [ 11 ] . These approaches have proven effective for homogeneous graphs and, in some cases, bipartite structures [ 1 , 7 ] . However, extending modularity-based objectives to higher-order relational structures remains challenging. Several extensions have been proposed for multipartite or multi-relational networks, but they typically rely on discrete optimization or strong structural assumptions [ 9 ] . In particular, tripartite graphs cannot be reduced to pairwise interactions without losing structural information, while explicit hypergraph formulations often lead to prohibitive computational costs or non-differentiable objectives [ 14 , 3 ] . In the field of graph learning, most deep clustering approaches for spatial or geographical data define neighborhoods using Euclidean distances or k -nearest-neighbor graphs [ 6 ] . Such heuristics ignore the physical constraints that structure real-world urban spaces and may introduce artificial connections between entities that are spatially close but topologically disconnected. In this work, we address these limitations by proposing a differentiable formulation of tripartite modularity tailored to graphs composed of three node types connected through mediated interactions. Our approach defines community structure in terms of weighted co-paths across the tripartite graph and relies on a factorized computation that avoids the explicit construction of dense third-order tensors. A structural normalization at the pivot nodes is introduced to handle extreme degree heterogeneity and ensure stable optimization, in line with previous extensions of modularity to heterogeneous settings [ 8 ] . 2 Data and Methodological Construction This section describes the construction of the tripartite graph and the associated methodological choices. The graphs considered in this work fall within the broader category of heterogeneous graphs, for which numerous graph neural network architectures have been proposed in recent years [ 13 ] . The urban data mobilized here provide a realistic validation setting, enabling the evaluation of the model’s behavior on a large heterogeneous graph, without constituting a thematic or application-driven analysis objective in itself. 2.1 Data Sources and Graph Ontology The graph is constructed by integrating several French administrative registries: the cadastral register (parcels), the National Address Base (BAN), and the National Building Repository (RNB), which serves as an interoperability pivot between the different sources. These datasets are selected for their exhaustive coverage, stable structuring, and topological consistency, which are essential properties for evaluating a large-scale graph learning framework. The resulting graph G=(V,E) is composed of three distinct types of nodes: • X : addresses, • Y : buildings, • Z : cadastral parcels. Edges are strictly typed: • E_{XY} : access or association relations between an address and a building, • E_{YZ} : implantation relations between a building and one or more parcels. No direct edge is defined between node sets X and Z . Tripartite interactions emerge exclusively through the pivot set Y , in accordance with the observed structure of the data. The proposed framework therefore relies on the existence of co-paths connecting X\rightarrow Y\rightarrow Z . As a consequence, nodes in X or Z that are not connected to any pivot node in Y do not participate in the tripartite dynamics and are excluded from the effective graph used for learning. This structural hypothesis is consistent with the modeling objective, which explicitly targets interactions mediated by pivot nodes. 2.2 Limitations of Geometric Neighborhoods In many works in geospatial graph learning, the neighborhood is defined based on Euclidean proximity criteria, typically via k -nearest neighbor ( k -NN) graphs. While these constructions are simple to implement, they present a major limitation in an urban context: they ignore the real physical constraints that structure the space. Two spatially close entities may be separated by a strong topological discontinuity (roadway, distinct land ownership), while more distant entities may be functionally and morphologically connected. The use of purely geometric neighborhoods thus introduces artificial edges that do not correspond to observable physical relations, biasing the input graph structure. 2.3 Topological Construction Constrained by the Cadastre To avoid these biases, the graph topology is derived directly from the cadastral structure. Relations between parcels are defined based on their physical contiguity, weighted by the length of the shared boundary. For two parcels P_{i} and P_{j} , the edge weight is defined as: w^{ZZ}_{ij}=\log\left(1+\text{length}(\partial P_{i}\cap\partial P_{j})\right). (1) The transformation \log(1+\ell) applied to lengths aims to compress the weight dynamics while preserving their relative ordering. It prevents a small number of exceptionally long edges from dominating the aggregation process, without introducing an arbitrary threshold. Other monotonic increasing functions with a similar saturation effect lead to comparable behaviors; this choice is not critical for the proposed method. Connectivity between buildings is then obtained through a dual topological projection of the parcel graph. Let M^{YZ} denote the building–parcel incidence matrix; the resulting topological adjacency between buildings is given by: A^{YY}_{\text{topo}}=M^{YZ}\cdot A^{ZZ}\cdot(M^{YZ})^{\top}. (2) This construction guarantees that two buildings are connected only if they rest on parcels that are themselves connected (figure 1 ), thereby preventing the creation of edges that arbitrarily cross public space. The projection is implemented using sparse matrix operations, ensuring linear complexity in the number of edges. Figure 1: Comparison of graph construction strategies on a residential area. Left (Method A): Standard k-NN graph (k=8) based on Euclidean distance. Note that edges (red dotted lines) arbitrarily cross the roadway, creating artificial connections between distinct urban blocks. Right (Method B): The proposed Dual Topological Projection. Orange lines represent common parcel boundaries (weighted by length, Eq. 1 ). Green lines represent the resulting connectivity between buildings. The topology strictly respects the street layout: no edge connects separated blocks, despite their geographic proximity. 2.4 Attribute and Position Encoding Each building-type node is associated with an attribute vector describing elementary geometric properties (area, compactness, elongation, convexity). These descriptors are chosen for their scale invariance and their ability to differentiate built forms without resorting to explicit functional categories. To introduce absolute