Synchronization on group-labelled multigraphs

Group synchronization refers to the problem of inferring the un- known values attached to vertices of a graph where edges are la- belled with the ratio of the incident vertices and labels belong to a group. This work addresses for the first time the group synchronization problem on multigraphs, that is, graphs with more than one edge connect- ing the same pair of vertices. The problem arises naturally when multi- ple measures are available to model the relationship between two vertices. This happens when different sensors measure the same quantity or when the original graph is partitioned into subgraphs that are solved independently. In this case the relationships among subgraphs give rise to multi-edges and the problem can be traced back to a multigraph synchronization problem. The solutions appeared so far reduce multigraphs to simple ones by aver- aging their multi-edges, however this approach falls short because: i) has been studied only for some groups and ii) the resulting estimator is less sta- tistically efficient than our solution, as we prove empirically. Specifically, we present a solution based on a principled constrained eigenvalue opti- mization that copes with general groups and can be profitably used both on synthetic and real multigraph synchronization problems.

La sincronizzazione su gruppi è il problema di riconstruire i valori sconosciuti corrisponenti ai vertici di un grafo etichettato, i cui archi sono anch’essi etichettati dal rapporto tra gli elementi associati ai due vertici incidenti. In questo elaborato si considera, per la prima volta, il caso in cui la sincronizzazione è applicata a multigrafi, ovvero grafi che ammettono più di un singolo arco tra una qualsiasi coppia di vertici. Questo problema si presenta naturalmente quando sensori diversi misurano la stessa quantità o quando il grafo originale è partizionato in sotto-grafi indipendentemente sincronizzati. In questo caso, le relazioni tra sotto-grafi danno origine a multi-archi e il problema può essere ricondotto a un prob- lema di sincronizzazione su multigrafo. Le soluzioni attuali riducono il multigrafo ad un grafo semplice facendo la media degli elementi associati ai multi-archi. Questo approccio presenta serie limitazioni in quanto: i) è stato finora considerato solo per alcuni gruppi and ii) lo stimatore che si ottiene è meno efficiente a livello statistico della nostra soluzione, come di- mostrato empiricamente. Nello specifico, in questo elaborato presentiamo una soluzione basata su un problema di ottimizzazione di autovalori vinco- lati che non è limitata a gruppi specifici e che garantisce ottimi risultati su grafi sia sintetici sia reali.