Rémi Vaudaine

Pierre Borgnat

Paulo Goncalves

Rémi Gribonval

Márton Karsai
email: mkarsai@ceu.edu

Temporal network compression via network hashing

Keywords: Temporal networks, out-component calculation, streaming matrix algorithms, graph hashing

Pairwise temporal interactions between entities can be represented as temporal networks, which code the propagation of processes such as epidemic spreading or information cascades, evolving on top of them. The largest outcome of these processes is directly linked to the structure of the underlying network. Indeed, a node of a network at given time cannot affect more nodes in the future than it can reach via time-respecting paths. This set of nodes reachable from a source defines an out-component, which identification is costly. In this paper, we propose an efficient matrix algorithm to tackle this issue and show that it outperforms other state-of-the-art methods. Secondly, we propose a hashing framework to coarsen large temporal networks into smaller proxies on which out-components are easier to estimate, and then recombined to obtain the initial components. Our graph hashing solution has implications in privacy respecting representation of temporal networks.

Introduction

While temporal networks represent the sequence of time-evolving interactions between entities, they also code the connected structure that lays behind many dynamical processes like the spreading of an epidemic or an information cascade or the collective adoption of behavioural norms or products. In static networks, connectivity is conventionally defined between two nodes if they are connected via a direct edge, or via a path building up from a sequence of adjacent edges that (pair-wise) share at least one node [START_REF] Newman | Networks[END_REF]. In temporal networks, however, connectedness is coded by temporal paths that are constructed from adjacent temporal interactions, which are not simultaneous yet structurally adjacent, and respect the causal time order. They determine the set of reachable nodes that can be influenced in the future with information held by a given node at a given time [START_REF] Badie-Modiri | Efficient limited-time reachability estimation in temporal networks[END_REF][START_REF] Holme | Temporal networks[END_REF]. The set of reachable nodes of a node at a given time, also called its influence set, is the node's temporal out-component, whose structure and size are important indicators of any ongoing dynamical processes. Indeed, no ongoing process can exhibit a larger collective pattern than the largest connected out-component in the underlying temporal network. However, the characterisation of connected components in temporal networks is a difficult task, as the temporal ordering of interactions introduces a degree of complexity to detect time-respecting paths in an effective way. Here, we address this challenge by defining a component matrix that codes the inand out-component size of any node in a temporal network. Using this matrix we apply network compression and reconstruction techniques via graph hashing, to estimate the distribution of the size of connected components of nodes. The proposed algorithm provides advancements in the computation efficiency of the largest node components compared to the state-of-the-art, specifically for temporal networks with large number of interactions.

Calculation of the largest out-component:

Considering all nodes and timed interactions in a temporal network, the most important component to characterise is, among other components, the largest out-component that ever emerged in the structure. Its identification can be approached using different ideas. A simple one would be to simulate a deterministic Susceptible-Infected (SI) process starting from every node at their first interaction time. In a deterministic SI process, nodes are either in a susceptible (S) or infected (I) state and a susceptible node certainly becomes infected when interacting with an infected one. It is a conventional model to describe the fastest spreading process in a network, where starting from a single seed node at its first appearance, the downstream set of infected nodes determines its maximum out-component. Using this method, in a temporal network of n nodes and m events, the computation of the out-component of a spreading seeded from a single source node, at its first appearance time would have O(n) space and O(m) time complexity (in terms of memory usage and computation time). This results in O(n 2 ) space and O(nm) time complexity when considering every node.

A more efficient method rely on temporal Event Graphs (EG), a higher-order representation of temporal networks [START_REF] Mellor | The temporal event graph[END_REF][START_REF] Kivelä | Mapping temporal-network percolation to weighted, static event graphs[END_REF][START_REF] Badie-Modiri | Efficient limited-time reachability estimation in temporal networks[END_REF]]. An EG is a static and lossless representation of a temporal network in the form of a weighted and directed acyclic graph (DAG). In this structure, temporal interactions are associated to nodes that are linked if their corresponding events are adjacent. For a more precise definition see Section. 2. Computing a single traversal of a static event graph (in reversed time order) yields the out-component of any node at any time, with an evidently smaller computational complexity as compared to a direct computation on a temporal network. However, EG appears with considerably larger size (having as many nodes as events in the original temporal network) and higher link density (by connecting any events to all future adjacent others) that leads to increased memory complexity. In order to reduce memory complexity, a link reduction method has been proposed that eliminates path redundancy in the EG [START_REF] Mellor | The temporal event graph[END_REF][START_REF] Kivelä | Mapping temporal-network percolation to weighted, static event graphs[END_REF], leaving the connectedness of the DAG intact. Relying on the reduced EG, the use of the approximate HyperLogLog (HLL) counting algorithm can further reduce the time complexity of the out-component detection to O(m log(m) + η), where η is the number of edges of the EG. However, this method provides only estimation for the size of out-components, without giving any information about their detailed structure.

Graph compression for component inference:

Contrary to earlier solutions, our idea is to use graph compression methods to compute the outcomponent size distribution of a temporal network, with a reduced computational complexity. The compressibility of static networks has been studied recently [START_REF] Lynn | Quantifying the compressibility of complex networks[END_REF], and has been shown to depend on the structure of the graph. This notion can be extended for temporal networks by interpreting them as a sequence of time-aggregated static network snapshots. Then compression can be formulated as finding a smaller diffusion-equivalent representation [1]. Also, consecutive snapshots can be compressed depending on their chronological importance [START_REF] Allen | A network compression approach for quantifying the importance of temporal contact chronology[END_REF]. Moreover, as pointed out by Li et al. [START_REF] Li | Compression of spatio-temporal networks via point-to-point process models[END_REF], in spatio-temporal networks nodes can be compressed via local clustering, while reducing time instants to change-points. Compression can be formulated using Minimum Description Length to also reduce the size of the graph [START_REF] Liu | Reducing large graphs to small supergraphs: a unified approach[END_REF]. Another compression approach has been proposed using information theory considerations, aiming to reduce the number of bytes required to describe a temporal network [START_REF] Liakos | On compressing temporal graphs[END_REF][START_REF] Caro | Compressed kd-tree for temporal graphs[END_REF]5]. Reducing the size of the network via coarsening to compute spectral properties of a graph has also been studied [START_REF] Loukas | Spectrally approximating large graphs with smaller graphs[END_REF]. Sampling techniques have been largely used to reduce the complexity of computation over large graphs [START_REF] Yousuf | Guided sampling for large graphs[END_REF].

Despite these numerous compression techniques proposed for temporal networks, none of them reduces effectively the number of nodes in a series of events. This reduction has a huge impact on the computational complexity of any of these algorithms, especially when they are characterised by quadratic complexity in the number of nodes. Thus our central question remains: how to design an efficient compression scheme that reduces the number of nodes while keeping enough information about the network itself to reconstruct the statistics of its connected components?

To reduce the computational complexity of the out-component size distribution calculation, we first propose a online streaming matrix algorithm that scans through the series of events only once, while it can also consider new events added later on, without re-starting the computation. In addition, we define a general purpose temporal network compression scheme using a graph hashing approach. This compression method reduces the total number of nodes, yet it requires a decompression scheme too, which provides only an approximate solution. The compression method can be used in conjunction with the matrix algorithm and, more generally, it can be applied on any temporal network algorithm.

To present our contributions, we organised the paper as follows. First, we formalise the problem of out-components computation in Section 2. We present the proposed novel streaming matrix algorithm to compute the distribution of the size of out-components in Section 3, including some numerical experiments. Then, we describe the hashing framework in Section 4, and we report also on the numerical studies carried out to evaluate its ability to estimate the ground-truth outcomponents' distributions in Section 4.4. Finally, we discuss the proposed methods and the results.

Methods

The aim of the present work is to effectively compute the distribution of the maximum outcomponent size for all nodes in a temporal network. To establish our apporach, we introduce first the definitions that are necessary to ground our methodology.

Problem definition

We define a temporal network G := (V, E, T ) as a series of temporal events e = (u, v, t) ∈ E that record interactions between nodes u, v ∈ V at time steps t sampled1 from a T time periods of length T . The network G is characterised by its number of nodes n = |V| and its number of events m = |E|. In G we call two events e i ∈ E, e j ∈ E adjacent if they share at least one node ({u i , v i } ∩ {u j , v j } ̸ = ∅) and their inter-event time is ∆t = t j -t i > 0, i.e. the two events are not simultaneous. Furthermore, we call two events to be δt-adjacent if they are adjacent and their inter-event time is ∆t ≤ δt. A sequence of adjacent events defines a time respecting path between nodes u and v starting at time t, if the first event of the path starts from node u at time t, the last ends at node v, and each consecutive events in the sequence are pairwise adjacent [START_REF] Holme | Temporal networks[END_REF]. The set of nodes that can be reached by any paths starting from node u at time t defines the out-component. The size of the out-component of a node u at a given time t is measured as the number of unique nodes that can be reached by valid time respecting paths. Actually, it determines the largest possible phenonenon (e.g., largest epidemic or information cascade) that was initiated from that source node and evolved in the future. The computation of out-components is computationally challenging as it requires the tracking of each time-respecting paths starting from each node at each time. However, an effective approximate solution has been proposed lately [START_REF] Badie-Modiri | Efficient limited-time reachability estimation in temporal networks[END_REF] to solve a partial challenge, to estimate only the size of out-components without keeping track of nodes involved.

Event graphs and the HyperLogLog algorithm

The proposed solution builds on the Event Graph (EG) representation [START_REF] Kivelä | Mapping temporal-network percolation to weighted, static event graphs[END_REF][START_REF] Mellor | The temporal event graph[END_REF] of temporal networks. An event graph G := (V, E, ∆t) is defined as a static weighted directed acyclic graph (DAG) representation of a temporal network G, where temporal events are associated to nodes in G (i.e., V = E); directed edges in G correspond to ∆t-adjacent event pairs in the original temporal network, with direction indicating their temporal order. The ∆t weight of each link is defined as the inter-event time between the two adjacent events corresponding to the connected nodes in G. This way, an event graph has m = |E| number of vertices and η number of directed edges. This static graph representation provides a losless description of a temporal network and can be exploited to infer several property of G without computations on the temporal structure [START_REF] Kivelä | Mapping temporal-network percolation to weighted, static event graphs[END_REF]. Indeed, thanks to the EG representation, the out-component size distribution of G can be precisely computed [START_REF] Badie-Modiri | Efficient limited-time reachability estimation in temporal networks[END_REF], yet with high computational and memory costs.

To reduce this cost at the price of an inexact computation, Modiri et al. [START_REF] Badie-Modiri | Efficient limited-time reachability estimation in temporal networks[END_REF] proposed an approximate solution to precisely estimate the out-component size distribution of a temporal networks using its EG representation combined with the HyperLogLog algorithm.

The HyperLogLog (HLL) algorithm takes as input a set, and it outputs an approximate of its size [START_REF] Flajolet | Hyperloglog: The analysis of a nearoptimal cardinality estimation algorithm[END_REF]. More precisely, a HLL structure uses a representation on s registers each storing a number, initialised to zero to start with. Every element of the set is hashed into a binary vector that is then cut in two parts. The first part indicates the identifier of the register that will be used and the position of the leftmost 1 in the second part is stored in that register if it is larger than the current value. Finally, the size of the set is estimated with an ensemble indicator function based on the registers. The main advantage of the algorithm is that the whole set is not stored to estimate its size and the estimation can be done with constant space and time complexity O(s). The error of the estimation is O(1/ √ s). Also, the size of the union of two sets can also be estimated in constant time and space by merging two HLL structures. A final property is that each element of the set is considered one by one, hence compatible with a streaming approach. Let us stress that the hashing functions used in HLL are not related to the ones we will use in Section 4 to compress the network representation.

The HLL algorithm can be used to estimate out-component sizes in a EG without tracking the exact set of nodes involved [START_REF] Badie-Modiri | Efficient limited-time reachability estimation in temporal networks[END_REF]. This approach reduces the time complexity of the out-component distribution computation to O(m log(m)+η) up to some constant factors that depend on the hyper parameters s of the HLL algorithm, which sets the trade-off between computational efficiency and accuracy.

Streaming matrix algorithm for out-component size calculations

We develop a streaming matrix algorithm as an exact solution for the question of computing the largest out-component of each node in a temporal network. The proposed solution can process chronologically streamed nodes and events of a temporal network in real time, with a space complexity that does not depend on the number m of events.

To demonstrate the basic idea of the method, let us consider the simple example of an information spreading process on a temporal network between n nodes modelled by a deterministic SI process (a short definition is recalled in the Introduction). To follow-up on the evolving components during the SI process, we design a matrix with rows representing the in-component and columns representing the out-component of each node. At time t = 0, when each node has a unique information that it has not propagated yet to any other nodes, we obtain the identity matrix with ones in the diagonal and zeros otherwise. Propagation happens between nodes u and v at the time of their interactions, when they mutually share all unique information they already learned from others (including their own) during earlier times of the process2 . This propagation rule is associated to the "OR" operation between the corresponding lines of the matrix, which yields the union of the set of unique information known by the two nodes. By the last event of the temporal network, the unique information of a node u is known by all other nodes in its out-component (depicted by column of the matrix). Thus, to compute the size of u's out-component, we simply have to count the number of unique nodes that are aware of u's unique information, i.e., the number of ones in the corresponding column of the matrix.

The component matrix

The component matrix is a binary matrix of size n × n, where n is the number of nodes in G. An illustration is provided in Fig. 1. An element (i, j) of the matrix is 1 if and only if the node i is reachable from the node j by any temporal path. Thus, the i-th line of the component matrix is the in-component of the node i and the j-th column of the matrix is the out-component of the node j.

Temporal network

Component matrix

1 2 3 4 5 3 1 5 4 t 0 t 1 t 2 t 3 2 1 2 3 4 5
Out-component of node 3

Figure 1: Left: a temporal network defined as a series of events ordered in time (t i < t j for i < j). The out-component of node 3 is circled in blue; the in-component of node 2 is circled in purple. Right: the corresponding component matrix. A row depicts the in-component of a node (we emphasise that of node 2). A column depicts the out-component of a node (we emphasise that of node 3): a non-zero element in the u-th column at coordinate v, means that node v belongs to the out-component of node u.

Algorithm 1: The matrix algorithm Data: Time ordered list of events E Result:

Component matrix S 1 S ← I n ; // Initialization 2 for e in E do 3 u ← e[0] 4 v ← e[1] 5 r ← S[u] OR S[v] ; // Compute the binary OR 6 S[u] ← r ; // Replace row of u by r 7 S[v] ← r ; // Replace row of v by r 8 end
The precise algorithm to compute this component matrix is given as pseudo-code in Algorithm 1. It starts with the identity matrix. Then, for every event, the lines corresponding to the interacting nodes are used to compute a binary OR operation, and those lines are replaced by that resulting OR. Finally, at the end of the series of events, the output matrix is the component matrix. This algorithmic construction process is described in Fig. 2. Since we use a n × n matrix to store the intermediate results, the space complexity is O(n 2 ), which may be reduced using sparse matrices for storage. For time complexity, we can divide the algorithm into several steps. The initialisation of the identity matrix can be done in O(n) by simply setting the n diagonal elements to the "True" value at the outset. To update the matrix we perform the OR operation between two vectors of size n once for each of the m events. The complexity of each update is O(n), bounded by the maximum out-component sizes n, but could be further reduced with a sparse matrix format. Consequently, the total complexity of the updates is O(nm). Finally, counting the number of non-zero element (or non-"False" elements) can be done at the same time as the update without any added complexity. Thus, the overall time complexity of the component matrix algorithm is

Complexity of the algorithm

O(n) + O(nm) = O(nm).

Streaming computation of average out-component size

One way to further reduce the complexity of the computation is to look for an approximation of the average size of a maximum out-component rather than its exact size. This can be implemented with the component matrix using the HyperLogLog counting algorithm that has been recalled before. It allows us to approximately describe and count the "True" values on each row of the matrix. The rows of the component matrix describe a set of nodes: the in-component. An HLL structure of size s (arbitrarily chosen, independently of n and m) can be used to estimate the size of an in-component. Thus, n HLL structures replace the former matrix. In its matrix form, the algorithm starts with the identity matrix. For the HLL structures, we simply initialise them with a single element: the i-th structure will be initialised with "i". Then, for every event (i, j, t), the OR operation between the lines i and j of the matrix is computed, which is equivalent to the union of the two in-components. For the HLL structures, this results in merging them. Finally, every HLL structure can give an approximation of the size of its corresponding line in the component matrix. Interestingly, the average size of the maximum out-components at time t is defined as:

st = 1 n u∈V v∈V S t (u, v), (1)
where the sums are interchangeable. Thus it can be computed both as the average size of outcomponents or in-components. Actually, the HyperLogLog structure can compute a size estimate with no additional cost in O(1) time complexity for each in-component, which are coded in the matrix as the number of "Trues" in a row. According to Eq. 1, the average value of these maximum in-component size values can give us an estimate directly for the average of the maximum outcomponent sizes. Thus, the HyperLogLog approach can reduce the algorithm's space complexity to O(n) and the time complexity to O(m) 3 . As an advantage, the matrix algorithm using Hyper-LogLog preserves the streaming aspect of the algorithm, assuming events to arrive in chronological order. However, in turn, it does not provide the whole maximum out-component size distribution but only an estimation for its mean value.

Component size distribution from reversed event sequence

By reversing time, we can easily obtain a solution to compute the whole maximum out-component size distribution. But it comes at the expense of losing the streaming property of our algorithm, as this solution takes as input, the whole interaction sequence in reversed order, processing it from the end to the beginning. By reversing the order of the sequence of events, the in-components become the out-component. In this case the component matrix algorithm does not fuse the rows anymore but it has to be adjusted the fuse the columns instead. Thanks to the reversal of the sequence of events, we can use the HyperLogLog counting method to estimate the full distribution of the maximum out-component sizes at a lower cost.

More specifically, for every node, we initialise a HyperLogLog structure with constant size, which contains only the node itself as previously. Then, for every event (u i , v i , t i ), considered in reverse chronological order, we merge the structures of u i and v i (corresponding to columns, i.e., to current estimates of out-components) in O(1) time. Finally, we approximate the size of the maximum out-component of every node with their HyperLogLog estimates. This results in having an approximation for the whole distribution of out-components' sizes in O(n) space complexity, O(m) time complexity, and scanning the events' sequence only once. While this seems to be a very efficient solution, the constants in the complexity evaluations are quite large in practice, setting back the effective performance of this solution in some regimes of n and m, as we demonstrate in the next section, while providing better results in others.

Method

As a summary, the first part of Table 1 reports on the complexity and properties of the methods described so far. The second part of the table also anticipates on the method to be described in the next section.

Experimental validation

We perform several computational experiments to demonstrate the effectiveness of the component matrix algorithm and to compare its performance to the corresponding EG based solution.

Experimental setting:

To test the performance of these algorithms we consider a simple model of temporal network. We first generate a static undirected random graph G(n, p) using the Erdős-Rényi model with n nodes and wiring probability p = 2/n. This way the constructed static graph will likely contain a unique giant component. To generate a temporal network, we set an independent Poisson process on each link [START_REF] Badie-Modiri | Efficient limited-time reachability estimation in temporal networks[END_REF] of this graph to determine the times when links are present and can transmit information between connected nodes. This way, both the underlying structure and the link dynamics are generated by random processes, that induce limited degree heterogeneity (with an emerging Poisson degree distribution) [START_REF] Albert | Statistical mechanics of complex networks[END_REF] and no burstiness (with exponential interevent time distribution) [12]. In the simulated networks, the number of nodes n varies between {100, 200, 500, 1000, 2000, 5000, 10000} and the number of events m logarithmically from 10 to 10 8 . Note that while real temporal networks may exhibit several types of structural and temporal heterogeneity, we assume they would not change considerably the conclusion of the performance evaluation provided here.

For a fair comparison, both the EG based and the component matrix based methods were used to solve the same task, that is to compute the largest maximum out-component size of a temporal network. While the EG based method solves a larger problem first, i.e. estimating the out-component size of any node at any event, one can extract the maximum out-component size for every node from its solution, simply by taking the size that corresponds to the first emergence of a given node. The overall asymptotic memory and time complexity of this solution scales similarly to the EG+HLL algorithm [START_REF] Badie-Modiri | Efficient limited-time reachability estimation in temporal networks[END_REF], as it is summarised in Table 1. Taking this model as reference, we compare it with the performance of the proposed proposed method based on the exact component matrix, as well as with its variant which uses HLL algorithms to obtain an approximation. In each method using HLL, we tune s to obtain less than 1% error for the average component size. Note that reversing time does not change neither the time nor the memory complexity of the component matrix algorithm with or without HLL as summarised in Table 1.

Results:

To compare the different methods, we report in Fig. 3 the ratio of computation times and of memory usages between the compared algorithms. First, let us focus on the relative performance of the component matrix method in Fig. 3 (a) and (c). Interestingly, results depicted in panel (a) suggest that although this method provides an exact solution for the task, it performs always better than the EG+HLL algorithm in terms of computation time. A similar scaling is true in terms of memory complexity (panel (c)), although the large quadratic cost of the component matrix makes this method to perform worst than the reference for small numbers of events or for large numbers of nodes. Nevertheless, we can conclude that the component matrix method largely outperforms the event graph method in terms of computational time and memory for large numbers of events, especially with networks of smaller size, where the gain can reach several orders of magnitude.

Comparing the HLL variant of the component matrix algorithm with the reference EG+HLL mode, show more variable performance. In terms of computational time (see panel (b) in Fig. 3), although worse for small numbers of events and large networks, the performance of our method is comparable to that of the exact method, for the other parameter values. However, regarding memory consumption (see (d)), our method is much more efficient, as it does not have to store the component matrix of size n 2 . For large network sizes the model requires approximately the same memory size as the reference model, while it is doing significantly better for the rest of the parameter space.

Advantages and limitations:

As stated before, a major advantage of the component matrix algorithm as compared to other methods is its space complexity that does not depend on the number m of events in the temporal network but scales as the square of its node set size n. Meanwhile, its time complexity scales only linearly with m. This is especially suitable for data streaming scenarios when nodes and events arrive in chronological order. Actually, adding a new node to the network requires only to add a new row and column to the component matrix set as "False", except the diagonal element. As for new events, insertion follows the update rule discussed earlier, as the algorithm operates in a streaming manner. Furthermore, the component matrix method requires only one pass over the event sequence. At any time step t when a new event appears, it only requires information about the previous state of the component matrix S i-1 at time t -1 (or conversely in the case of reversed time). On the other hand, the exact component matrix method scales poorly in space complexity in terms of n, the number of nodes, as it operates on a n×n matrix. This shortcut can be addressed by the HLL method to obtain approximate results. A sparse matrix implementation can also be very beneficial to solve this problem, if the average out-component size is much smaller than n. Otherwise, when it is comparable to n and the number of non-zero elements in the matrix is in O(n 2 ), even a sparse matrix solution would scale quadratically.

Reference point:

The figure above only gives the ratio between the computation times or the amount of memory required for the computations. We provide in Table 2 some reference points for the real values for each method. The smallest temporal network on Fig. 3 is for n = 100 and m = 100. The largest temporal network in Fig. 3 is for n = 10 4 and m = 10 8 . The associated computation times and memory usages are reported in Table 2.

Hashing the temporal network

Hashing the temporal network consists in reducing its number of nodes, thus compressing it, by (randomly) assigning nodes of the initial temporal network to "super-nodes" of a hashed graph. An event, or an interaction, between two nodes at time t in the initial temporal network becomes a new event between their hashed representatives in the hashed graph at time t. Reducing the number of nodes is notably attractive because this reduces the complexity of various different algorithms including the computation of the component matrix, even though this may cause information loss about the initial graph. To balance this effect, we propose to use several different hashing functions and to fuse the obtained results together. The overall framework is shown in Fig. 4.

Temporal network 3 1 5 4 t 0 t 1 t 1 t 1 t 0 t 0 t 0 t 2 t 3 2 ... S (1) 0 S 4 ... S 0 S 4 A'' B'' C'' A''B''C'' ... A'' B'' C'' A''B''C'' S (3) 0 S 4 A B C A' B' C' A'' B'' C'' t 1 t 3 t 3 t 3 t 2 t 2 t 2 1 2 3 4 5 1 2 3 4 5 S 4 A' B' C' A' B' C' A' B' C' A' B' C' A B C A B C A B C A B C Hashing Fusion h 2 h 2 h 3 h 3 h 1 h 1
Figure 4: From a 5 nodes temporal network, several hashed version are computed with 3 nodes each. Then, every hashed graph can be used to compute a small component matrix thanks to our matrix algorithm. Finally, the different component matrices can be fused to compute an approximate solution of the component matrix of the initial temporal network.

Hashing functions

To reduce the number of nodes of the static graph underlying the input temporal graph (in short: "the input static graph"), and therefore the computation complexity of the out-component size distribution, we use hashing functions. These functions take as input a set of labels of n nodes, {1, ..., n} = [n], and hash them into n s super-nodes {1, ..., n s } = [n s ]. The labels are the nodes of the input static graph and the buckets are the super-nodes of the resulting hashed static graph. Since n s < n, some nodes will collide into the same super-node, reducing the overall cost of computation over the hashed temporal network associated to the hashed static graph, but reducing also the amount of available information. We use k-universal (randomised) hashing functions [START_REF] Thorup | Tabulation based 4-universal hashing with applications to second moment estimation[END_REF].

A class H of random functions is k-universal if ∀x 1 , ..., x k ∈ [n], ∀v 1 , ..., v k ∈ [n s ], Pr{h(x i ) = v i , ∀i ∈ [k]} = 1/n k s (2)
where the probability is on the draw of h. Qualitatively, this means that, the probability that one node of the initial graph is assigned to the same super-node by two different hashing functions is low and controlled by the choice of k.

In our work, we use k = 4 and the hashing functions are based on a large prime number: P rime = 2 61 -1. First, let us define the table A of size (3, order), where order is an order parameter, as:

∀i ∈ {0, 1, 2}, ∀j ∈ [order], A(i, j) = ((rand(2 31 -1) ≪ 32) + rand(2 31 -1))%P rime (3)
where ≪ 32 denotes the shift of the binary representation 32 bits to the left.

The number acc is computed recursively order -1 times thanks to:

acc(i, u) = M ultAddM od(u, acc(i, u), A(i, j))%P rime (4)
where j ∈ {1, ..., order}, M ultAddM od is a function defined in the paper and initially, acc(i, u) = A(i, 0). Then, T 0 , T 1 , T 2 are tables of size n s that are defined as:

∀u ∈ [n s ], T i [u] = acc(i, u) (5)
Furthermore, for every node, we define three quantities x 0 , x 1 , x 2 as ∀u ∈ [n], x 0 (u) = low(u), x 1 (u) = high(u), x 2 (u) = x 0 (u) + x 1 (u) where low(u) outputs the 32 rightmost bits of the binary representation of u and high(u) outputs the 32 leftmost bits. Finally,

∀u ∈ [n], h(u) = T 0 (x 0 (u)) ⋆ T 1 (x 1 (u)) ⋆ T 2 (x 2 (u)) (6)
where ⋆ is the bitwise exclusive OR.

The hashed static graph is made of super-nodes defined by the output of a hash function and of "super"-edges connecting them: if u and v connected in the initial static graph, then the super-nodes h(u) and h(v) become connected by a super-edge, whose weight is binary. Finally, for every event (u, v, t), a super-event is defined as (h(u), h(v), t).

Fusion to compute the distribution of out-components

The main goal of our work is to compute the out-component, or its size, of every node in the input temporal network with lower complexity than existing methods reported in Table 1. To do so, we hash the set of n nodes of the input temporal network into n s super-nodes with K different hash functions h j .

∀i

∈ [n] ∀j ∈ [K], h j (u i ) ∈ [n s ] (7)
These hashing functions are drawn independently at random. Here, the hashing functions h j , ∀j ∈ [K] are not injective thus not invertible: there are usually several nodes mapped to the same super-node. We define the inverse of h as the function that, given a super-node of the hashed static graph, computes the set of corresponding nodes in the initial static graph:

∀v ∈ [n s ], h -1 (v) = {u ∈ [n]/h(u) = v} (8)
Denote OC(u) (resp. OC(h(u))) the out-component of node u (resp. super-node v = h(u)). Assuming we can compute (an estimate of) the out component OC(v) of a super-node v in the hashed graph obtained with hashing function h j , we can also define

h -1 j (OC(v)) = x∈OC(v) h -1 (x) (9)
Instead of estimating the out-component for each of the n nodes in the temporal network, we first hash the network into K hashed graphs of n s nodes and m events, then estimate the out-component for every node in the hashed graphs and finally aggregate the information by intersecting the (estimated) out-components given by each hashed graph. We then define

∀i ∈ [n], OC(u i ) = j∈[K] h -1 j (OC(h j (u i ))). (10)
The estimated out-component necessarily contains the true out-component, i.e. OC(u i ) ⊆ OC(u i ), yet if K is too small the set OC(u i ) may be much larger than the true out-component. Computing | OC(u i )|, where |A| is the number of elements of a set A, one can compute an approximation of the distribution of the out-components' sizes with any of the aforementioned algorithm that is able to compute the out-components (and not only their sizes) on the hashed graphs. We compare the resulting approximate distribution with the true distribution.

Properties of the algorithm

The structure of the resulting algorithm ensures that every step before the final fusion remains compatible with streamed events arriving in chronological order, and is also amenable to parallel/independent computations for each hashing function.

Moreover, the complexity of the framework depends on the setup. In a parallel setting, i.e. when the S (k) i are computed separately, we need O(K ×n 2 s ) space to store the matrices and O(mn s ) time to compute the small component matrices. In a non-parallel setting, we need O(K × n 2 s ) to store the small matrices and O(Kmn s ) time to compute them.

Experimental evaluation

The compression framework that we propose can be used with several observables. Here, we focused on the computation of the out-components. The whole distribution of the size of the out-components describes the largest spreading phenomena possible starting from every node. The other quantity we are interested in is the tail of the distribution, i.e. the set of nodes with largest out-component' size. To experimentally prove the effectiveness of our work, we measure the precision of the approximate method with respect to the ground-truth for both the distribution and its tail.

Experimental setting:

For simulations, temporal networks are generated exactly as in the previous Section, see 3.4. In the generated data, the number of nodes, n, varies between {100, 200, 500, 1000, 2000, 5000, 10000} and the number of events varies between 10 4 to 10 9 as powers of 10. The number of super-nodes is always a fraction of the number of nodes: n s = 0.3 × n and the number of hashing functions is

K = 5.
The baseline algorithm is our matrix method from the previous section since it provides the exact distribution of the size of the out-components, with a controlled memory and time complexity. The results will compare the hashing version to this baseline.

In addition, some experiments have been conducted on real-world datasets freely available in Snap. The "Superuser" temporal network is a network of interactions on the stack exchange web site Super User. There are three kinds of interactions (edges): a user (node) answered a question of someone else, a user commented a question or a user commented an answer. The Superuser network is made of 194 085 nodes and 1 443 339 events. The "Reddit" dataset is a temporal network of connections between subreddits (i.e., forum dedicated to a specific topic on the website Reddit), taken here as nodes. There is an event between two subreddits when there is a post from a source subreddit that links to a target subreddit. The Reddit temporal network has 35 776 nodes and 286 560 events.

For real datasets, we split chronologically the events in 10 equal parts and compute the distribution of the largest out-component on {10%, 20%, ..., 100%} of the events. As for generated datasets, we use n s = 0.3 × n. We also use K = 1 and K = 5. The baseline is still the matrix algorithm of the previous section.

Performance criteria:

We evaluate the hashing framework based on three criteria: time, memory and accuracy. We compare the time required by the matrix algorithm to compute the true distribution of the largest out-components, D with the one required by the hashing framework to compute the approximate distribution of the largest out-components D s . The computation time of the hashing framework includes both the computation of the hashed matrices and their fusion.

We also compare the memory usage of the matrix algorithm, with a single big matrix, with the one of the hashing framework, with several smaller matrices.

Furthermore, to compare the ground-truth out-component' size distribution D and the one computed thanks to the hashing framework D s (n s , K), we simply use the Earth-Mover distance, also called Wasserstein distance [START_REF] Bonneel | Displacement interpolation using Lagrangian mass transport[END_REF], computed thanks to the Python Optimal Transport library [START_REF] Flamary | Pot: Python optimal transport[END_REF], but any distance between two distributions could be used. We also tried to use the Kullback-Leibler divergence but it was less sensitive to subtle differences between the distributions. Thus we can define accuracy of the out-component size distribution inference as:

Acc(n s , K) = γ(D, D s (n s , K)) (11)
where γ is the Earth-Mover distance. The lower Acc(n s , K), the closest are the two distributions.

Results

First, we present the result for the generated data. The relative computation time, relative memory usage and accuracy of the hashing framework are reported in Fig. 5. The relative computation time figure is red meaning that the hashing framework requires more time than the matrix method to compute the target distribution. However, we can clearly see that the relative computation time decreases quickly with the number of events and slowly with the number of nodes. Generally, for datasets with more events than m = 10 8 , the hashing framework with K = 5 and n s = 0.3 × n requires less time than the full matrix method.

For the relative memory usage, the figure is blue meaning that we always gain memory. In fact, in this setup, only half the memory of the matrix method is required for the hashing framework. As for the Earth-Mover distance, there is a regime for small datasets where the accuracy is not Figure 6: Relative computation time and relative memory usage for the Reddit and Superuser datasets to compute the distribution of the largest out-components thanks to the hashing framework compared to the matrix method depending on the number of nodes n. satisfactory but for the large majority of the generated datasets, the hashing framework performs very well.

For the real datasets, we first show the results of the relative computation time and the relative memory usage of the hashing framework compared to the matrix method in Fig. 6. Experimentally, we show that the hashing framework generally requires more time to compute the target distribution. Moreover, the relative computation time is linear with the number of hashing functions. That is, for K = 5, that time is approximately 5 times higher than for K = 1 for both the Reddit dataset and the Superuser dataset. Overall, the general shape of the curves is in line with the results of generated data. For example, the relative computation time for the third point of the Reddit dataset, n = 15370 and m = 85968, is 198, which coincide with the corresponding value of the generated datasets. Overall, the relative computation time decreases as the number of nodes increases, as expected.

Then, the memory required for the computation is linear with the number of hashing functions. We clearly see that, for K = 5, the memory usage is 5 times more than the one for K = 1. The figures for real datasets are also in line with the figures for generated datasets. Obviously, with K = 1 and n s = 0.3×n, the computation requires less memory than with the full matrix algorithm for both real datasets by a factor 10. But, more importantly, with K = 5 and n s = 0.3 × n, the hashing framework still requires only around 50% of the memory of the matrix method.

Finally, we report the accuracy of the hashing framework compared to the matrix method in terms of the Earth-Mover distance between the true distribution computed by the matrix method and the one estimated by the hashing method in Fig. 8. Indeed, the quality of the results is important to assess the quality of the hashing framework. For both datasets, lower dimensions lead to lower accuracy of the framework. We see that the first few points, corresponding to networks of small sizes, have a significantly higher Earth-Mover distance (thus, lower accuracy) than the remaining ones. Overall, the shape of the curves still confirms the results with the generated datasets: the larger the network, the better the approximation. Secondly, as expected, the distance is lower for higher values of K. The accuracy of the method increases as there are more hashing functions.

Thus overall we can conclude that hashing is relevant in high dimension. There is a computation time gain for m ≥ 10 9 in the generated datasets while memory usage remains lower and accuracy is good. Also, increasing the number of hashes leads to a linear increase in the memory usage and a linear increase in the computation time. Obviously, this increases the accuracy of the method.

Conclusion

The continuous growth in the size of data bases requires new algorithms to process information. Moreover, structured data evolving over time represents an important challenge since it differs a lot from usual tabular data. To that end, we proposed a matrix algorithm that is able to compute both Figure 8: Accuracy for the Reddit dataset and the Superuser dataset to compute the distribution of the largest out-components thanks to the hashing framework compared to the matrix method. the out-components for every node of a temporal network and their sizes. Furthermore, to reduce the complexity of the analysis, we proposed a compression scheme based on hashing function that reduces the number of nodes of the network at the cost of some uncertainty. Uncertainty is lifted thanks to the use of several hashes in parallel. On each hashed graph, the matrix algorithm can be computed and, finally, all the information is merged to approximate the component matrix of the input network. Our framework is online and allows parallelization. Indeed, new nodes and news events can be processed as they come. Moreover, the different hashed graphs allow parallelization since they are independent. Additionally, hashing can make the computation private. If we do not observe the temporal network directly but only hashed versions of it and if hashes have some external randomness, our framework allows ϵ-differential privacy [START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF]. We believe that our work has a lot of potential applications. The first concrete user case is to use out-component sizes as the maximum number of nodes reachable during a spreading process. For example, it can be the maximum number of people infected by a virus from a single source. Or, on Twitter, it can be the maximum number of people a piece of news spread to. Secondly, our framework can be extended to other cases. In our work, we focused on out-components but we believe that many other quantities can be computed thanks to our compression scheme such as pairwise distances between nodes. Also, we believe that the hashing framework can be rewritten with an algebraic formulation. This would open up the work to linear problems and linear solvers. In fact, the reconstruction of the matrix could be tackled in many different ways making the framework more flexible. Moreover, privacy preserving algorithms are particularly interesting for security or privacy reasons. The work we propose can efficiently make algorithms on temporal networks private. Indeed, adding randomness in the data can lead to prevent the identification of the source of the data. Most importantly, our hashing framework transforms a temporal network into a series of smaller datasets that can be used to infer properties of the initial dataset without direct access to it. This can be very beneficial in the processing of sensitive information.

Figure 2 :

 2 Figure2: From a given temporal network (left graph), we compute the Component Matrix (right matrix) of size n × n, with n = 5, by scanning the series of events. For each event, we compute the OR operation between the rows of the matrix corresponding to the interacting nodes and replace them by the result. Matrix S 4 is the component matrix at the end of the streaming after m = 4 events.

Figure 3 :

 3 Figure 3: Fraction of computational time (top row) and memory usage (bottom row) of the component matrix methods divided by the ones of the EG+HLL method. Panels (a) and (c) results for the exact component matrix method, while panels (b) and (d) are for its approximate solution using HLL. All scales are logarithmic with colour blue indicating when the component matrix method performs better (and red in the contrary case).

  Figure 5: a) Relative time and b) relative memory usage for the computation of the distribution of the largest out-components compared to the ground-truth given by the matrix method on synthetic data. c) Accuracy of the hashing framework given by the Earth-Mover distance.

Figure 7 :

 7 Figure 7: Relative computation time and relative memory usage for the Reddit and Superuser datasets to compute the distribution of the largest out-components thanks to the hashing framework compared to the matrix method depending on the number of events m.

Table 1 :

 1 Summary of methods used to compute the maximum out-component size distribution. Time and space complexity depends on the number of nodes n and events m, and number of edges η in the event graph (EG). Column entitled "Exact" indicates if the method provides exact (Yes) or approximate (No) solution. The column called "Stream" indicates if the method can stream events in chronological order. Column "OC" shows if the method can compute not only the out-component sizes but the involved nodes as well. The column "P (|OC|)" shows if the whole out-component distribution (Whole) or only its average (Average) can be computed. The hashing framework is described in the next section, with n s number of super-nodes, K number of hashing functions, and // indicating the possible parallelisable method. Note about the Matrix method: its space complexity is in O(n 2 ) but can be reduced to O(sn log n) where s is the average size of out-components in the case of sparse matrices.

		Time cpx.	Space cpx. Exact Stream OC P(|OC|).
	EG + HLL	O(m log(m) + η) O(m + η)	No	No	No	Whole
	SI process	O(mn)	O(n 2 )	Yes	No	Yes	Whole
	Matrix	O(mn)	O(n 2 )	Yes	Yes	Yes	Whole
	Matrix + HLL	O(m)	O(n)	No	Yes	No	Average
	Matrix + reverse t	O(mn)	O(n 2 )	Yes	No	Yes	Whole
	Matrix + reverse t + HLL	O(m)	O(n)	No	No	No	Whole
	Matrix + hashing (//) Matrix + hashing	O(mn s ) O(mn s K)	O(n 2 s K) O(n 2 s )	No No	Yes Yes	Yes Yes	Whole Whole

Table 2 :

 2 Computation times and memory usage for the EG + HLL, Matrix and Matrix + HLL methods for n = 100 and m = 100 (first and second line) and for for n = 10 4 and m = 10 8 (third and fourth line).

		EG + HLL Matrix Matrix + HLL
	Time (ms)	40.3	0.4	27.4
	Memory (kB)	1	80	0.92
	Time (s)	30172	700	811
	Memory (MB)	200000	800	0.085

In these definitions, we neglect the duration of events for simplicity, but all definitions could incorporate durations in a straightforward way.

Information sharing could be deemed non-mutual in case of directed interactions in the temporal network.

Remember, however, that the O(•) notation hides a constant, whose value results from a trade-off between cost and precision for the HLL algorithm.

Acknowledgement

This work has been supported by the DATAREDUX project, ANR19-CE46-0008. MK was supported by the CHIST-ERA project SAI: FWF I 5205-N; the SoBigData++ H2020-871042; the EMOMAP CIVICA projects; and the National Laboratory for Health Security, Alfréd Rényi Institute, RRF-2.3.1-21-2022-00006. PB was supported by the CHIST-ERA-19-XAI-006, for the GRAPHNEX ANR-21-CHR4-0009 project.


M Gaide

D Marcheix

A Arnould

X Skapin

H Belhaouari

S Jean

Automatic detection of topological changes in modeling operations

Keywords: Topology-based modeling, Topological change detection, Static analysis, Graph transformation rules, Generalized maps, Orbite type Detected event Orbite type Detected event

Advanced geometric modelers require the detection of topological changes caused by modeling operations such as edge creation, face splitting or volume merging... Such a detection can be dynamically performed by comparing all topological cells (vertices, edges, faces, volumes) before and after each modification, which can be very time consuming. Then, for some events generated in a systematic way, it can also be performed statically before applying each operation, but it entails several hurdles due to the lack of formalization of such events: while some events may seem obvious, others may not appear intuitively or systematically, and this work of defining events needs to be done again for each newly developed operation. In this paper, we propose to formalize the static detection of events and to automate this process based on automatic analysis of operations. To achieve this, we leverage on the formalism of graph transformation rules to describe geometric operations, and on the topological model of G-maps that enables homogeneous modeling of manifold geometric objects in any dimension. The syntactic analysis of rules enables the detection of all events that can be detected statically and also specifies the cells on which events that can only be detected dynamically could occur. With this approach, any new operation can be developed faster within the modeler, ensuring a complete, accurate and automatic event detection.

Introduction

CAD-oriented systems rely on geometric modeling kernels which allow users to design and maintain control over complex geometric models [Das23; Ope22; Sie22]. An essential feature of such kernels is event detection: the ability to track topological changes (creation, deletion, split, merging and modification) of cells (vertices, edges, faces, volumes) when a modeling operation is applied.

Event detection has a variety of purposes such as, for example, the construction of event logs, per-

The definitive version of the paper is available at https: //diglib.eg.org/xmlui/handle/10.2312/cgvc20231186 sistent naming schemes or modeling optimization. An event log is an history-based data structure describing the evolution of cells during the construction of a model. Such data are required for the internal execution of a number of operations provided by kernels and are also passed through the API in order to help developers using those kernels to maintain model consistency [ABC00; Bab+07; Liu+18; Ope22]. A persistent naming scheme allows the reevaluation of models regardless of parameter changes, or their transfer toward other systems, and directly or indirectly depends on events detection to propose unique and persistent names for cells [Kri95; MP02; Che+12; BNB05; FH18].

Events detection is also useful for optimizing the modeling process. For example, operation conflicts in feature-based collaborative CAD systems can be detected and resolved by tracking topological entity changes [Che+16].

Most current tools detect events dynamically. A dynamic detection requires comparing a model before and after the application of any operation [Ope22; Bab+07]. On complex models that contain a significant number of cells, the cost in time to fully perform event tracking can be relatively high. To reduce this cost, it is possible to statically detect some local events. For example, the triangulation of a face generates vertex modifications, vertex creations, face subdivision, and so on. Static detection is based on analyzing operations and allows events to be described and calculated before those operations are actually performed. It is up to the developer of the operation to manually define and describe these events, which raises a number of predicaments. First, there is currently no standard formalization for describing these events. For instance, depending on the system, an edge flip operation between two triangles may be interpreted as a modification of both triangles or as a split and/or merging of those triangles. Second, the task of defining and describing events needs to be repeated every time a new operation is developed. Third, this manual definition can introduce errors because while some events may seem obvious, others may not be intuitively apparent or can be forgotten. Event detection may then be incomplete or erroneous. For example, consider the edge collapse operation used in geology for studying soil erosion [Béz+14]. This operation is illustrated in Fig. 1. Quite intuitively, the collapse of an edge results in the merging of both vertices at its endpoints. This can be observed in Fig. 1b, where vertices V 1 and V 2 are merged into a single vertex S 1 . However, when the same operation is applied again (Fig. 1c), it leads to the merging of vertices S 1 and V 3 and the subsequent split into two vertices S 2 and S 3 , in the case of a classical manifold representation. The same operation applied to an edge of a cylinder can even result in no vertex merging at all, but only a split (Fig. 1e).

In this paper, we propose to formalize the static detection of local events and automate this process based on automatic analysis of operations. To achieve this, we use the formalism of graph trans- formation rules to describe geometric operations, specifically using the Jerboa library [Bel+14] which facilitates the development of modelers dedicated to specific applications. Jerboa is based on the Generalized Maps (or "G-maps") topological model [Lie91; DL14], which corresponds to a specific class of labeled graphs and enables homogeneous modeling of oriented or non-oriented manifold geometric objects in any dimension. The rules are constructed through the Jerboa interface, which allows for rapid development of modeling operations while ensuring the topological consistency of the underlying geometric model. As we show in the following, a syntactic analysis of each rule enables the detection of local events and also specifies the cells on which global events could occur (events that can only be detected dynamically). This detection becomes much faster, as only these cells need to be verified during the application of the operation. With this approach, any new operation can be developed within the modeler, ensuring an automatic, complete and accurate event detection.

Section 2 introduces the concepts of generalized maps and Jerboa's graph transformation rules, along with their associated vocabulary. Section 3 formalizes topological events and details the static analysis to perform in order to automatically detect these events. Section 4 presents an example of event log integrating a list of automatically detected events. Section 5 provides a time cost comparison between static and dynamic event detection. Section 6 concludes and proposes some perspectives.

Main concepts

In this section, we present the generalized maps, the graph transformation rules, and the concepts upon which our method is based.

Generalized maps

Generalized maps (or G-maps) [Lie91; DL14] allow the representation of manifold geometric objects (with or without boundaries), based on some cellular n-dimensional topological structure.

The representation of an object as a G-map intuitively comes from its decomposition into topological cells (vertices, edges, faces, volumes, and so on). For example, the 2D geometrical object shown in Fig. 2a is represented as a 2-dimensional G-map (or 2-G-map) as follows. The object is first decomposed into faces (Fig. 2b). These faces are linked along their common edge with a 2-link, drawn in blue. Each edge on the border of the object is connected to itself (the blue 2-link forms a loop). The index "2" means that the link connects two 2dimensional (possibly a single one) faces. In order to simplify the reading, 2 labels will not be written in every subsequent figure. In the same way, faces are split into edges connected with red 1-links (Fig 2c). Lastly, edges themselves are split into vertices with black 0-links (Fig 2d) to produce the 2-G-map describing the objects shown in Fig. 2a. A G-map is therefore a graph, the nodes of which are the vertices (named darts) obtained at the end of the process and the edges are i-links.

G-maps have conditions guaranteeing objects consistency: for example, two faces are always linked along an edge.

Topological cells are not explicitly represented in G-maps but only implicitly defined as subgraphs. They can be computed using graph traversals defined by an originating node and by a given set of link labels named orbit. For example, the 2-cell adjacent to some dart a (or the object face matching a) (Fig. 3a) is the subgraph which contains a and all darts reachable from a, using links labeled 0 or 1 (i.e. darts a, b, c, d, e, f , g and h) and the links themselves. This subgraph is denoted by G⟨0, 1⟩(a) and models the face BCED (Fig. 2a). ⟨0, 1⟩ is the type of the orbit. The 1-cell adjacent to a (or the object edge matching a) (Fig. 3b) is the subgraph G⟨0, 2⟩(a) which contains a and all reachable darts using links labeled 0 or 2 (i.e. darts a, b, l and m) and the corresponding links. It represents the topological edge BC. Thanks to 2-loops on the object border, G⟨0, 2⟩(c) (Fig. 3c) also represents the edge CE matching dart c. The 0-cell adjacent to a (or the object vertex matching dart a) (Fig. 3d) is the subgraph G⟨1, 2⟩(a) and represents vertex B. Note that orbits are more general than cells. For example, the face edge G⟨0⟩(a) (Fig. 3e) is an ⟨0⟩ orbit adjacent to a.

Graph transformation rules

Jerboas's [Bel+14] graph transformation rules allow the formalisation of operations over G-maps.

In a few words, a rule r : L -→ R and a match m : L → G to a G-map G, describe the transformation G -→ r,m H from G to H. m allows replacing a sub-graph of G described by the left-hand side of the rule L with another one described by the right-hand side R, in order to produce H.

Informally, in the triangulation rule shown in Fig. 4, the left side is made of only one node n 0 labeled with the ⟨0, 1⟩ (i.e. face) type: this way, it can match any face. Consider for instance the node n 0 from L and the dart a 0 from G shown in (Fig. 5a), respectively. Matching n 0 with a 0 , the whole face G⟨0, 1⟩(a 0 ) is matched, highlighted in orange in the figure. 0-(resp. 1-) links are represented by black (resp. red) segments. On the right side, the node n 0 has label ⟨0, _⟩. This means that when applying this rule, 0-links of nodes n 0 have been preserved, while 1-links have been deleted. Hence, in H (Fig. 5b), the 0-links of the matched orange face have been preserved while 1-links have been deleted. In other words, the edges of the orange face are disconnected in H. The new node n 2 of R creates, in H, darts copied from the matched face. This is why there are eight blue darts (a 2 , b 2 . . . h 2 ) created from orange darts (a 0 , b 0 . . . h 0 ). Because n 2 is labeled ⟨1, 2⟩, the orange 0-(resp. 1-) links on the left side of the rule are relabeled to 1-(resp. 2-) links in the blue copy. Therefore, the rule creates a dual vertex to the matched face. Finally, the node n 1 of R creates a green copy with eight darts (a 1 , b 1 . . . h 1 ), deletes the left-side 0-links and relabels the left-side 1-links to 2-links.

All the highlighted links (Fig. 5) are referred to as implicit links in the rule nodes. Conversely, the links connecting the nodes together in R are re- ferred to as explicit links. For example, the explicit 0-links between n 1 and n 2 link one-to-one green and blue darts. Therefore, the rule creates the four new edges ⟨0, 2⟩ in the triangulation of the matched square face. By the same token, the explicit 1-link between n 0 and n 1 link one-to-one orange and green darts.

The n 0 node (Fig. 4) is a preserved node because it belongs to both the left and right sides of the rule. Nodes n 1 and n 2 are created nodes because they belong only to the right side of the rule. This rule does not contain any deleted node because none of its nodes belongs only to the left side.

The concept of orbit is extended to patterns of rules. For example, in the right-hand side of the triangulation rule (Fig. 4), the ⟨0, 2⟩-orbit (an edge) incident to node n 0 contains the single node n 0 , and the ⟨0, 2⟩-orbit incident to n 1 contain the two nodes n 1 and n 2 and the explicit 0-link which connects them. Additionally, an ⟨o⟩-orbit is said to be complete if each node in the orbit matches one link per label of ⟨o⟩ either explicitly or implicitly. For example, the ⟨0, 2⟩-orbit incident to node n 0 in the right-hand side of the triangulation rule (Fig. 3) is not complete, because node n 0 has no 2-link, neither implicitly nor explicitly. Conversely, the ⟨0, 2⟩-orbit incident to n 1 is complete, because its two nodes n 0 and n 1 are incident to the explicit 0link and both have an implicit 2-link. Note that an ⟨o⟩-orbit in a graph is entirely matched by a rule pattern if and only if the corresponding ⟨o⟩-orbit in the pattern is complete. For example, the ⟨0, 2⟩orbit incident to a 0 in the graph H (Fig. 5b) is partially matched by the triangulation rule (only darts 4) on matched dart a 0 a 0 and b 0 are matched and not their 2 neighbors), because the ⟨0, 2⟩-orbit incident to n 0 in the rule is not complete. Conversely, the ⟨0, 2⟩-orbit incident to a 1 in graph H is entirely matched by the triangulation rule (both darts a 1 and h 1 are matched by node n 1 and darts a 2 and h 2 are matched by node n 2 ), because the ⟨0, 2⟩-orbit incident to n 1 in the rule is complete.

a 0 b 0 c 0 d 0 e 0 f 0 g 0 h 0 (a) Graph G a 0 b 0 c 0 d 0 e 0 f 0 g 0 h 0 a 1 b 1 c 1 d 1 e 1 f 1 g 1 h 1 a 2 b 2 c 2 d 2 e 2 f 2 g 2 h 2 (b) Graph H
Jerboa's rules provide syntactic properties guaranteeing the preservation of G-maps consistency.

Event detection

Basically, detecting an event occurring on an orbit after the application of a rule implies comparing the graph before and after this application [Tie+17]. However, many events can be statically detected before the rule is applied. As seen previously, entrusting the developer with the task of detecting and formalizing these events for each new operation paves the way to various issues. We propose to formalize the different events (creation, deletion, split, merging, modification, and non-modification) and their detection in order to automate this process through analysis and comparison of rules' nodes.

Creation

Any node of a rule matches at least one dart. So when a rule creates a node, it also creates the corresponding darts. If the right-hand side of a rule contains a created orbit, then applying this rule on any object creates one or several orbits. For example, the triangulation rule (Fig. 4) creates the edge orbit R⟨0, 2⟩(n 1 ). Therefore, the application of this rule on the square face (Fig. 5) creates four edge orbits H⟨0, 2⟩(a 1 ), H⟨0, 2⟩(c 1 ), H⟨0, 2⟩(e 1 ) and H⟨0, 2⟩(g 1 ) in H.

The creation of an orbit is defined as follows : From the syntactic analysis of a rule, it is then possible to automatically detect the event of orbit creation using the following proposition : The orbit H⟨o⟩(d) is created if and only if R⟨o⟩(n) is created.

Definition 3.1.1 (Orbit creation) Let r : L -→ R be a rule, m : L → G a match, t : G -→
Idea of proof: Thanks to the syntactic conditions on rules, the orbit R⟨o⟩(n) is complete. Thus, due to the application of rules, H⟨o⟩(d) is included in the image of R⟨o⟩(n). Therefore, all darts of H⟨o⟩(d) are created. Conversely, if H⟨o⟩(d) is created, then this orbit is included in the image of R⟨o⟩(n) and R⟨o⟩(n) is created. □ Back to the example of face triangulation (Fig. 4 and5), we follow the creation of an edge. The edge orbit R⟨0, 2⟩(n 1 ) in the triangulation rule is created because both its nodes n 1 and n 2 are created. In the transformation, n 1 matches eight darts, including for example dart a 1 , and n 2 also matches eight darts including dart a 2 . The edge orbit H⟨0, 2⟩(a 1 ) is created as well as darts a 2 , h 1 and h 2 (Fig. 5b).

Split

When a rule explicitly splits an orbit, it also splits the set of matched orbits. For example, the unsewing rule (Fig. 6) splits the edge orbit L⟨0, 2⟩(n 0 ) into a pair of edge orbits R⟨0, 2⟩(n 0 ) and R⟨0, 2⟩(n 1 ). Therefore, the first application of this rule (Fig. 7b) splits the edge into two edges H⟨0, 2⟩(a 0 ) and H⟨0, 2⟩(a 1 ).

A rule can also split an orbit implicitly. For example, the triangulation rule (Fig. 4) splits the face orbit L⟨0, 1⟩(n 0 ) along the second implicit links since on the right-hand side, every second implicit link of the nodes n 0 , n 1 and n 2 belonging to the face orbit R⟨0, 1⟩(n 0 ) is either deleted or different from 0 and 1. Hence, applying this rule (Fig. 5) splits G⟨0, 1⟩(a 0 ) into four face orbits H⟨0, 1⟩(a 0 ), H⟨0, 1⟩(c 0 ), H⟨0, 1⟩(e 0 ), H⟨0, 1⟩(g 0 ).

The split of an orbit is defined as follows : • Either explicitly if there exists a preserved node n ′ in L⟨o⟩(n) that does not belong to the same orbit in R, i.e. R⟨o⟩(n) ̸ = R⟨o⟩(n ′ );

• Or implicitly along the k-th implicit link if there exists in L⟨o⟩(n) a node for which the kth implicit link belongs to ⟨o⟩ and for all nodes n ′ in R⟨o⟩(n), the k-th implicit link is renamed outside of ⟨o⟩.

An orbit G⟨o⟩(d) is split in the transformation t if and only if there exists a preserved dart d ′ in G⟨o⟩(d), such that H⟨o⟩(d) ̸ = H⟨o⟩(d ′ ).

From the syntactic analysis of a rule, it is then possible to automatically detect the event of orbit split using the following proposition : Proposition 3.2.1 Let r : L -→ R be a rule , m : L → G a match, t : G -→ r,m H the transformation of G by (r, m), ⟨o⟩ an orbit type, n a preserved node of r.

If the orbit L⟨o⟩(n) is both complete and explicitly split in r, i.e. if there exists a preserved node n ′ in L⟨o⟩(n) such that R⟨o⟩(n) ̸ = R⟨o⟩(n ′ ), then for any preserved darts d and d ′ of t respectively matching R⟨o⟩(n) and R⟨o⟩(n ′ ), G⟨o⟩(d) is split in t into two orbits H⟨o⟩(d) ̸ = H⟨o⟩(d ′ ).

If the orbit L⟨o⟩(n) is both incomplete and implicitly split, the split may be confirmed dynamically on G.

Idea of proof: As a reminder, a complete orbit L⟨o⟩(n) entirely matches an orbit G⟨o⟩(d).

In the case of an explicit split in r from L⟨o⟩(n) to R⟨o⟩(n) ̸ = R⟨o⟩(n ′ ), since L⟨o⟩(n) is complete, then due to rules syntactic conditions, so are R⟨o⟩(n) and R⟨o⟩(n ′ ). Let d and d ′ be two preserved darts of t such that d (resp. Let us assume now that L⟨o⟩(n) is not complete. Let d and d ′ be two darts of G matched by L⟨o⟩(n) which are potentially split. Because L⟨o⟩(n) is not complete, G can contain some path between d and d ′ using only links labeled in ⟨o⟩ such that this path is not entirely matched by L⟨o⟩(n). Therefore, this path does not break during the transformation t and both d and d ′ remain in the same orbit in H: H⟨o⟩(d ′ ) = H⟨o⟩(d ′′ ). □ Referring to the example of the unsewing rule (Fig. 6), we follow the explicit split of an edge. The rule splits the edge orbit L⟨0, 2⟩(n 0 ) because both its nodes n 1 and n 2 form two distinct edge orbits R⟨0, 2⟩(n 0 ) and R⟨0, 2⟩(n 1 ). Rule application (Fig. 7b) entails n 0 (resp. n 1 ) matching both Continuing with the face triangulation rule (Fig. 4), we follow the implicit split event of a face orbit type ⟨0, 1⟩. The orbit L⟨0, 1⟩(n 0 ) contains node n 0 and matches a single set of darts which form a face orbit. The first implicit link of n 0 is 0 and the second implicit link is 1; both belong to orbit type ⟨0, 1⟩. However, the orbit R⟨0, 1⟩(n 0 ) contains nodes n 0 , n 1 , n 2 and none of them has either 0 or 1 as a second implicit link. Under this condition, we can state that the face triangulation rule splits a face into two or more faces. Applying this triangulation rule on the square face (Fig. 5), L⟨0, 1⟩(n 0 ) matches the face orbit G⟨0, 1⟩(a 0 )). Then, the square face is split into the four faces matching R⟨0, 1⟩(n 0 ): H⟨0, 1⟩(a 0 ), H⟨0, 1⟩(c 0 ), H⟨0, 1⟩(e 0 ) and H⟨0, 1⟩(g 0 ).

d ′ ) is matched by L⟨o⟩(n) and R⟨o⟩(n) (resp. L⟨o⟩(n ′ ) and R⟨o⟩(n ′ )). It follows that G⟨o⟩(d) is split into H⟨o⟩(d) ̸ = H⟨o⟩(d ′ ). If L⟨o⟩(n) is complete,
a 0 a 1 b 0 b 1 (a) Graph G u 0 u 1 v 0 v 1 a 0 a 1 b 0 b 1 (b) Graph H c 0 e 0 f 0 d 0 c 1 e 1 f 1 d 1 v 0 u 0 v 1 u 1 (c) Graph I c 1 e 1 f 1 d 1 (d) Graph J
Note that both proposition 3.2.1 and its proof idea mention that a split of an ⟨o⟩-orbit is guaranteed to happen in a graph transformation when the split is explicit and the orbit is complete in the rule. For example, let us consider the unsewing edge rule (Fig. 6) and its application on a surface (Fig. 7) again but this time, we focus on the surface orbit L⟨0, 1, 2⟩(n 0 ). The rule's nodes of this orbit all miss an 1-link and, thus, L⟨0, 1, 2⟩(n 0 ) is not complete. As we can see, upon the first application of the rule (Fig. 7b), the surface is not split, although the conditions given in the definition 3.2.1 are met. Yet, in this case, applying the unsewing rule a second time (Fig. 7c) actually splits the surface. Indeed, when an orbit is not complete, the pattern matches only a part of the orbit and detected events must be confirmed dynamically. Fortunately, even if detecting this potential split is a dynamic process, it is not time-consuming, because we know exactly which cell needs to be traversed and which alpha links can potentially generate this split.

Merging

Similarly to orbit split, there exist explicit and implicit merging orbits.

For example, in the explicit case, the sewing rule (Fig. 8) is the opposite of the unsewing rule (Fig. 6) for both the result of its application and its construction. Let us consider the square plan (Fig. 7) from H to G (Fig. 7b to Fig. 7a). The sewing rule merges two edge orbits L⟨0, 2⟩(n 0 ) and L⟨0, 2⟩(n 1 ) into a single edge orbit R⟨0, 2⟩(n 0 ). Therefore, applying the sewing rule merges two edges of H, H⟨0, 2⟩(a 0 ) and H⟨0, 2⟩(a 1 ), into one edge G⟨0, 2⟩(a 0 ).

The same goes for the implicit merging. For ex-ample, in the implicit case, the edge deletion rule (Fig. 9) merges the face vertex orbits mapped to L⟨1⟩(n 0 ) along the second implicit link. In fact, in the left-hand side of the rule, the second implicit link of n 0 is 2 and n 1 has no second implicit link.

In the right-hand side of the rule, the second implicit link of n 1 is rewritten as 1. It follows that the application of this rule (Fig. 7d) merges both I⟨1⟩(c 1 ), I⟨1⟩(d 1 ) into J⟨1⟩(c 1 ) and both I⟨1⟩(e 1 ), I⟨1⟩(f 1 ) into J⟨1⟩(e 1 ).

The merging of an orbit is defined as follows :

Definition 3.3.1 (Orbit merging) Let r : L -→ R be a rule, m : L → G a match, t : G -→ r,m
H a transformation of G by (r, m), ⟨o⟩ an orbit type, n a preserved node of r and d a preserved dart of t.

An orbit L⟨o⟩(n) is merged by the rule r:

• Either explicitly if there exists a preserved node n ′ , with L⟨o⟩(n) ̸ = L⟨o⟩(n ′ ), such that both n and n ′ belong to the same orbit in R, i.e. R⟨o⟩(n) = R⟨o⟩(n ′ ).

• Or implicitly along the k-th implicit link if there exists in R⟨o⟩(n) a node whose the kth implicit link belongs to ⟨o⟩ and for all nodes n ′ in L⟨o⟩(n), the k-th implicit link does not belong to ⟨o⟩.

Two different orbits G⟨o⟩(d) and G⟨o⟩(d ′ ), with d ′ a preserved dart, are merged in the transformation t if and only if H⟨o⟩(d) = H⟨o⟩(d ′ ).

From the syntactic analysis of a rule, it is then possible to automatically detect the orbit merging event :

Proposition 3.3.1 Let r : L -→ R be a rule, m : L → G a match, t : G -→ r,m H a transformation of G by (r, m), ⟨o⟩ an orbit type, n a preserved node of r.
If the orbit L⟨o⟩(n) is both complete and explicitly merged, i.e. if there exists a preserved node n ′ in r such that L⟨o⟩(n) ̸ = L⟨o⟩(n ′ ) and R⟨o⟩(n) = R⟨o⟩(n ′ ), then for any preserved darts If the orbit L⟨o⟩(n) is both incomplete and implicitly merged, the merge may be confirmed dynamically on G.

Idea of proof:

The idea is analogous to the one developed for Proposition 3.2.1.

If the orbit L⟨o⟩(n) is both complete and explicitly merged with another orbit L⟨o⟩(n ′ ), where n ′ is a preserved node of r, then R⟨o⟩(n) = R⟨o⟩(n ′ ). Because L⟨o⟩(n) is complete, L⟨o⟩(n) entirely matches G⟨o⟩(d) for any preserved dart d of t matched by L⟨o⟩(n). Due to the injection property of matching, for any preserved dart d ′ of t matched by L⟨o⟩(n ′ ), d ′ is not a dart of G⟨o⟩(n). In other words, G⟨o⟩(d) ̸ = G⟨o⟩(d ′ ). Finally, due to the rule application,

R⟨o⟩(n) = R⟨o⟩(n ′ ) implies H⟨o⟩(d) = H⟨o⟩(d ′ ).
If L⟨o⟩(n) is complete and if there is an implicit merge along the k-th implicit links of L⟨o⟩(n) in r, then by definition, all the k-th implicit links of L⟨o⟩(n) are deleted or named outside of ⟨o⟩. Let n ′ be a preserved node of L⟨o⟩(n) such that the k-th implicit link of n ′ is i-labeled in R with i in ⟨o⟩. Let d and d ′ be two darts, matched by n ′ , and i linked in H. Both Let us assume now that L⟨o⟩(n) is not complete. Let d and d ′ be two preserved darts of t matched by L⟨o⟩(n) which are potentially merged. Because L⟨o⟩(n) is incomplete, so is R⟨o⟩(n), and H can contain some path between d and d ′ using only links in ⟨o⟩ such that this path is not entirely matched by R⟨o⟩(n). Therefore, this path has not been built during the transformation t and d and d ′ were already in the same orbit in G (G⟨o⟩(d) = G⟨o⟩(d ′ )). □ With the example of the sewing rule (Fig. 8), we follow the explicit merging of two edges. The edge orbits L⟨0, 2⟩(n 0 ) and L⟨0, 2⟩(n 1 ) are complete and merged in the rule because their res-pective nodes n 1 and n 2 are part of the same edge orbit R⟨0, 2⟩(n 0 ). Applying the transformation, n 0 (resp. n 1 ) matches the darts a 0 and b 0 (resp. a 1 and b 1 ). Edge orbits H⟨0, 2⟩(a 0 ) and H⟨0, 2⟩(a 1 ) are merged into orbit G⟨0, 2⟩(a 0 ) (i.e. a 0 , b 0 , a 1 and b 1 ), as shown in Fig. 7a.

With the edge deletion rule (Fig. 9), we follow Then, the face vertices around the edge to delete is merged into the pair of face vertices matched from R⟨1⟩(n 1 ) (i.e. J⟨1⟩(c 1 ) and J⟨1⟩(e 1 )).

Note that a potential merge of two faces is also detected in this edge deletion rule. Indeed, the second implicit link of n 1 in R⟨0, 1⟩(n 1 ) does not appear in all nodes of L⟨0, 1⟩(n 1 ) but this orbit is not complete. Thus, such a potential merge is automatically detected and must be confirmed dynamically depending if both faces incident to the removed edge are different (as shown in Fig. 7d). Similarly, let us consider the first example from Fig. 1 that uses the edge collapse rule introduced in Fig. 10 and the incomplete L⟨1, 2⟩(n 0 ) orbit. The first application of the rule (Fig. 11b) does not result in a vertex split, while the second application does (Fig. 11c).

Other events

The approach for the other events (deletion, non modification and modification) being relatively similar, we will describe them in a more concise way.

Deletion

This event mirrors the creation one. Let us get back to the edge deletion rule (Fig. 9). This rule, as its name suggests, deletes an edge orbit L⟨0, 2⟩(n 0 ). Its single node n 0 , which by itself matches an edge because it is complete on ⟨0, 2⟩, no longer exists on the right side of the rule and, therefore, is deleted. Applying the rule on the darts shown in whose darts (c 0 , d 0 , e 0 and f 0 are then deleted in J (Fig. 7d), since there are no nodes in R to match them.

The deletion of an orbit is defined as follows : An orbit L⟨o⟩(n) is deleted in the rule r if all of its nodes are deleted in r.

An orbit G⟨o⟩(d) is deleted in the transformation t if and only if all of its darts are deleted by t.

From the syntactic analysis of a rule, it is then possible to automatically detect the orbit deleting event : Idea of proof: Thanks to the syntactic conditions on the rules, a deleted orbit is always complete. Consequently, the corresponding orbits are also completely deleted in the transformation. □

Non-Modification

An orbit is said to be not modified when its nodes and links remain unchanged. For example, in the triangulation rule (Fig. 4), the face edge orbit L⟨0⟩(n 0 ) only contains node n 0 and the same goes for the orbit R⟨0⟩(n 0 ). Considering that the implicit 0-link of n 0 is unchanged and that there is no other node in its orbit, we can state that the triangulation rule does not modify the face edges. Applying this rule on the house (Fig. 5), the face edge orbits remain the same and G⟨0⟩(a 0 ) = H⟨0⟩(a 0 ), G⟨0⟩(c 0 ) = H⟨0⟩(c 0 ), G⟨e 0 ⟩ = H⟨e 0 ⟩ and G⟨0⟩(g 0 ) = H⟨0⟩(g 0 ) (Fig. 5b).

The non-modification of an orbit is defined as follows :

Definition 3.4.2 (Orbit non-modification) Let r : L -→ R be a rule, m : L → G a match, t : G -→ r,m H the transformation of G by (r, m), ⟨o⟩ an orbit type, n a preserved node of r and d a preserved dart of t.

An orbit L⟨o⟩(n) remains not modified in the rule r if L⟨o⟩(n) = R⟨o⟩(n) and all the nodes of the orbit have the same label on both sides of the rule, i.e. their implicit links are the same in L and R.

An orbit G⟨o⟩(d) is said to be not modified in the transformation t if G⟨o⟩(d) = H⟨o⟩(d).

From the syntactic analysis of a rule, it is then possible to automatically detect the orbit nonmodification event :

Proposition 3.4.2 Let r : L -→ R be a rule, m : L → G a match, t : G -→ r,m H the transformation of G by (r, m), ⟨o⟩ an orbit type, n a preserved node of r and d a preserved dart of t.

If an orbit L⟨o⟩(n) remains not modified in the rule r, then G⟨o⟩(d) remains not modified in the transformation t for any dart d of G matched by L⟨o⟩(n).

If an orbit G⟨o⟩(d) is not matched by the rule, i.e. no dart of G⟨o⟩(d) is matched by L, then it remains not modified.

Idea of proof: This is obvious, because a rule may modify only the matched part of a graph. □

Modification

Generally speaking, an orbit is modified when it is neither created, deleted, not modified, split or merged. More specifically, a modified orbit has either modified links, some created part or some deleted part. Also, such a change must not lead to a split nor a merging event. For example, once again considering the triangulation rule, vertex orbit L⟨1, 2⟩(n 0 ) contains node n 0 only, while R⟨1, 2⟩(n 0 ) contains both nodes n 0 and n 1 . The orbit has a created part related to n 1 , the second implicit link of n 0 is deleted, and there is no split, either implicit or explicit: thus, the orbit is modified. Applying this rule on the house (Fig. 5) entails vertex orbits G⟨1, 2⟩(a 0 ), G⟨1, 2⟩(c 0 ), G⟨1, 2⟩(e 0 ), G⟨1, 2⟩(g 0 ) to be modified with an added part of two new darts each.

Event log

Event detection method, defined in a generic manner on rules in section 3, allows automatic generation of an event log encompassing all events or potential events that occurred on the object when a rule is applied. To illustrate this with a simple example, let us consider the Event log in Table .1. It corresponds to the application of the triangulation rule (Fig. 4) to the bottom face of the geometric object (Fig. 5). As we can see, events can be automatically detected and listed for each orbit. For the sake of simplicity, we have chosen a rule that matches a complete orbit. Thus, all events can be detected statically. If not, the event log specifies the precise orbit that needs to be dynamically verified.

Static and dynamic comparison

This section compares a dynamic approach, in which the program manages the evolution of the orbits while traversing a 3D object, with a static approach which exploits the techniques presented in this article. The comparison has been done on an Intel i9-11950H with 32GB under JDK 11. We focus our study on the three main events: creation, split and merge operations. Fig. 12 displays ex-Table 1: Extract from the Event log generated after applying the triangulation rule (Fig. 4) on the house in Fig. 5.

perimental results of our study which measure the computation time of a single representative of the target orbit as the dart with the lowest identifier.

Static detection aims at recomputing only modified orbits whereas the dynamic detection would cover the whole mesh. The performance of a creation operation, shown in Fig. 12a, results from a scenario where a shape is extruded several times so as to create a new volume (i.e. a new orbit ⟨0, 1, 2⟩). For every orbit type, the static detection is invariably better than the dynamic one. We note a peak with regard to the dart orbit type, corresponding to a specific case where this orbit requires a substantial treatment as darts are the lowest dimension entities and a fair amount of them are created in this scenario. However, the static detection significantly limits execution time. Orbit ⟨0, 1, 2, 3⟩ yields similar values for static and dynamic detection, caused by the same process. Fig. 12b shows execution time for the split operation. The study considers a cube where each face is split into four faces by applying the Catmull-Clark subdivision scheme [CC78]. Consequently, this example focuses on the detection of events over the face orbit ⟨0, 1⟩. The histogram confirms the efficiency of the static approach over dynamic detection. However, we note the presence of two peaks corresponding to volume orbits ⟨0, 1, 2⟩ and connected component orbits ⟨0, 1, 2, 3⟩. Moreover, these two peaks have the same values. This case results from the input mesh: as we start with one volume which contains a single connected component, and since the operation just splits faces without adding new volumes, then the number of faces increases and directly impacts the performance for computing static and dynamic evolutions, even if the number of volumes and connected components is still one. Fig. 12c shows execution time for a merging operation. The study starts from a stack of cubes where the faces shared between two cubes are successively deleted, resulting in the merging of the volumes and their adjacent border faces: we focus on detecting the merging events over volume face orbits ⟨0, 1⟩ Once again, the histogram confirms the efficiency of the static approach over dynamic detection.

Conclusions and perspectives

Event tracking is one of the core functionalities of geometric modeling kernels. This detection can be done dynamically by comparing each topological cell composing the geometric model before and after applying an operation, but it can represent a significant cost when the model becomes very large.

To reduce this cost, it is possible to statically detect some specific events, meaning that events generated in a systematic way are directly defined during the development of the operation. The responsibility is then left to the developer of the operation to define these events, but it entails several hurdles. Firstly, there is no formalization to describe these events. Secondly, it can lead to errors because while some events may seem obvious, others may not appear intuitively or systematically, or may be forgotten.

Ultimately, this work of defining events needs to be done again for each newly developed operation. For these reasons, we propose in this paper to formalize the static detection of events and to automate this process based on automatic analysis of operations. To achieve this, we leverage on the formalism of graph transformation rules to describe geometric operations, and on the topological model of G-maps that enables homogeneous modeling of manifold geometric objects in any dimension. The syntactic analysis of the rule enables the detection of all events that can be detected statically and also specifies the cells on which events that can only be detected dynamically could occur. This dynamic detection becomes much faster, as only these cells need to be verified during the application of the operation. With this approach, any new operation can be developed faster within the modeler, ensuring a complete, accurate and automatic event detection.

This approach leads the way towards future works. First, as of now, the operations that can be analysed are defined with a single rule. An improvement will be to adapt this method to higher level operations defined as scripts combining several rules. Second, most current persistent naming methods rely on the tracking of topological entities evolutions. Working on a complex model, or in case of frequent reevaluations of parametric models, the static tracking of topological entities should allow a significant improvement of the efficiency of persistent naming methods. This could be accurately evaluated by integrating this static tracking into parametric systems.

Figure 1 :

 1 Figure 1: Various edge collapses.

Figure 2 :Figure 3 :Figure 4 :

 234 Figure 2: Cell decomposition of a geometric 2D object

Figure 5 :

 5 Figure 5: Application of the triangulation rule (Fig. 4) on matched dart a 0

Proposition 3 . 1 . 1

 311 Let r : L -→ R be a rule, m : L → G a match, t : G -→ r,m H the transformation of G by (r, m), ⟨o⟩ an orbit type, n a created node of R and d a dart of H matched by n.

Figure 6 :

 6 Figure 6: Rule r : L -→ R of unsewing 2-links along an edge (⟨0, 2⟩-orbit)

Definition 3 . 2 . 1 (

 321 Orbit split) Let r : L -→ R be a rule, m : L → G a match, t : G -→ r,m H the transformation of G by (r, m), ⟨o⟩ an orbit type, n a preserved node of r and d a preserved dart of t.An orbit L⟨o⟩(n) is split in the rule r:

  and there is an implicit split along the k-th implicit links of L⟨o⟩(n) in r, then by definition, all the k-th implicit links of R⟨o⟩(n) are deleted or renamed outside of ⟨o⟩. Let n ′ be a preserved node of L⟨o⟩(n) with a kth implicit i-link with i in ⟨o⟩, and d and d ′ two i-linked matched darts of n ′ in G. Then d and d ′ may either belong to two different orbits in H (H⟨o⟩(d) ̸ = H⟨o⟩(d ′ )); belong to the same orbit in H if the sub-orbit is folded along the split ilink (H⟨o⟩(d) = H⟨o⟩(d ′ )); or be the same dart if the link is a loop (d = d ′ and therefore H⟨o⟩(d) = H⟨o⟩(d ′ )).

Figure 7 :

 7 Figure 7: (a) Initial graph G. (b) First application of the 2-unsewing rule (Fig. 6): pink darts. (c) Second application of the 2-unsewing rule: green darts. (d) Application of the edge deletion rule (Fig. 9): red darts.

Figure 8 :Figure 9 :

 89 Figure 8: Rule r : L -→ R of 2-sewing along two edges (⟨0, 2⟩-orbits)

  d and d ′ of t respectively matched by L⟨o⟩(n) and L⟨o⟩(n ′ ), G⟨o⟩(d) is merged with G⟨o⟩(d ′ ) in H, i.e. G⟨o⟩(d) ̸ = G⟨o⟩(d ′ ) and H⟨o⟩(d) = H⟨o⟩(d ′ ).

  d and d ′ belong to the same ⟨o⟩-orbit in H (H⟨o⟩(d) = H⟨o⟩(d ′ )). Then d and d ′ may either belong to two different orbits in G (G⟨o⟩(d) ̸ = G⟨o⟩(d ′ )); belong to the same orbit in G if the rule folds the sub-orbit along the i-link (G⟨o⟩(d) = G⟨o⟩(d ′ )); or finally be the same dart if the i-link is a loop (d = d ′ and therefore G⟨o⟩(d) = G⟨o⟩(d ′ )).

Figure 10 :

 10 Figure 10: Rule L -→ R of edge collapse

Figure 11 :

 11 Figure 11: Two successive applications of edge collapse rule (Fig. 10) on matched dart a 0 (a), then on on matched dart e 0 (b)

Definition 3 . 4 . 1 (

 341 Orbit deletion) Let r : L -→ R be a rule, m : L → G a match, t : G -→ r,m H the transformation of G by (r, m), ⟨o⟩ an orbit type, n a node of L and d a dart of G.

Proposition 3 . 4 . 1

 341 Let r : L -→ R be a rule, m : L → G a match, t : G -→ r,m H the transformation of G by (r, m), ⟨o⟩ an orbit type, n a node of L and d a dart of G. An orbit L⟨o⟩(n) is deleted in the rule r if and only if the orbit G⟨o⟩(d) is deleted in the transformation t for any dart d matched by L⟨o⟩(n).

Figure 12 :

 12 Figure 12: Comparison between static and dynamic event to track all orbits (the lower the better)

  r,m H the transformation of G by (r, m), ⟨o⟩ an orbit type, n a created node of R and d a dart of H matched by n.An orbit R⟨o⟩(n) is created in the rule r if all of its nodes are created in r.An orbit H⟨o⟩(d) is created in the transformation t if and only if all of its darts are created by t.

Creation H⟨2⟩(No modif H⟨2⟩(a