network analysts

Abstract: Network motifs, recurrent local patterns of interactions in graphs, provide fundamental insights on the interplay between structure and functionality in complex systems. Many real-world systems are not well represented by traditional static pairwise networks, as interactions may involve groups of nodes, occur over time, or encode directionality. In this paper, we introduce temporal motifs for hypergraphs and directed hypergraphs, extending motif analysis to timestamped many-body interactions. We formalize the corresponding mining problem, study the combinatorial structure of these motifs, and develop exact algorithms for their enumeration. In particular, we propose a dynamic programming algorithm that substantially reduces the computational cost of motif mining, achieving orders of magnitude speedups on empirical datasets. We also introduce a null model for temporal hypergraphs to assess the statistical over- and under-expression of motifs. Applying the proposed framework to real-world datasets from different domains, including face-to-face contacts, scientific collaborations, e-mail exchanges, and Bitcoin transactions, we show that temporal hypergraph motifs reveal distinct forms of local organization across systems. Finally, we demonstrate their use as an exploratory tool through focused case studies on persistent patterns in scientific collaborations and e-mail communications.

Abstract: We propose a local algorithm that computes an $\varepsilon$-approximate PageRank vector in the sense of Andersen, Chung, and Lang (ACL; Internet Math. 2007) with teleportation parameter $α$ in $\widetilde{O}\bigl(1 / \bigl(\sqrtα \, \varepsilon\bigr)\bigr)$ time with high probability, improving the $O\bigl(1/(α\varepsilon)\bigr)$ running time of their original local push method. Our method also applies to the $\ell_1$-regularized PageRank problem with a running time of $\widetilde{O}\bigl(1 / \bigl(\sqrtα \, ρ\bigr)\bigr)$ for regularization parameter $ρ$, giving a positive answer to the open problem posed by Fountoulakis and Yang (COLT 2022). Our faster primitive has the potential to improve a broad range of graph algorithms that rely on local push. For example, substituting our primitive into the ACL framework directly yields faster PageRank-based local graph clustering, and we also develop reductions that lead to faster algorithms for effective resistance estimation. Our main technical contribution is a potential-function analysis of a refinement of the active-set method of Wei and Yang (preprint 2026), which repeatedly invokes an SDD solver on the current active set of nodes and expands the set. We relate the potential decreases over consecutive blocks of expansions to show that the number of expansions is bounded by $\widetilde{O}\bigl(1 / \sqrtα\bigr)$.

Abstract: We show that there is a fixed planar graph $H$, namely the $5 \times 5$ grid, such that Max Independent Set remains NP-hard in $H$-induced-minor-free graphs. This refutes the Dallard--Milanič--Štorgel conjecture and a weakening of it by Gartland and Lokshtanov, and by Korhonen.

Abstract: Graph condensation aims to produce a small surrogate graph that preserves the downstream node-classification performance of a much larger original graph. Existing methods rely on Weisfeiler-Lehman neighbourhood aggregation or gradient-based distribution matching, both of which assume that adjacent nodes share the same label, an assumption that breaks down under heterophily. We propose HERALD (High-fidelity Exemplar Retrieval with Adaptive Landmark Distillation), a gradient-free graph condensation framework that adapts the node scoring and feature selection in the condensation pipeline to the graph's measured heterophily. HERALD selects features via a joint Fisher-discriminability and activation-density criterion that down-weights aggregated representations on heterophilic graphs, and scores nodes by a weighted combination of prototype representativeness, decision-boundary proximity, and Local Intrinsic Dimensionality (LID), where the weights are driven by a smooth sigmoid function of the heterophily ratio. Nodes are then assembled into a condensed subgraph through score-ordered BFS expansion, Personalised PageRank pruning, and class rebalancing, all at an identical storage budget to BONSAI, enabling direct comparison. Experiments on eight benchmark datasets spanning homophilic and heterophilic settings show that HERALD matches or outperforms state-of-the-art condensers on heterophilic graphs and remains competitive on homophilic ones across four GNN architectures.

Abstract: Graph Neural Networks (GNNs) are powerful models for handling attributed graphs in tasks such as classification, link prediction, and community detection, as they enable the aggregation of information from both structural and semantic sources. However, progress in community detection is hindered by the lack of high-quality datasets, since ground-truth community labels are often unavailable and most algorithms proposed in recent literature rely on the same benchmark datasets for model training and evaluation. To address this issue, attributed random graph generators are commonly employed to create synthetic graphs for assessing the strengths and limitations of GNN-based models. Nevertheless, most existing generators rely heavily on power-law degree distributions, despite recent evidence indicating that scale-free networks are rare, particularly in social network contexts. Moreover, state-of-the-art attributed graph generators provide limited flexibility, as they do not allow users to construct communities with varying densities, degree distributions, and sub-community structures. To overcome these limitations, we introduce the Synthetic Community-Aware Attributed Graph Generator (SynCo), a graph generation algorithm that allows users to control the node degree distribution and sub-community structure. We evaluate SynCo across three different tasks: graph mimicking, hyperparameter evaluation, and node clustering tuning. The results show that our model outperforms state-of-the-art approaches in synthetic graph generation and data augmentation, while preserving the original distributions of duplicated and augmented datasets, as confirmed by statistical tests well know in literature. We also demonstrate the ability of SynCo to generate nodes in large scale, up to 2.1 million nodes.

Abstract: The goal of degree sequence reconstruction is to recover the ordered vector of degrees of an unknown graph from vertex deleted traces, where each vertex is deleted independently with probability $p$. We provide two algorithms for reconstruction; the first uses rejection sampling to reduce the problem to an estimation problem for a mixture distribution. Combined with prior trace reconstruction results, this gives a reconstruction algorithm using $\Exp{\tilde O (n^{1/3})}$ traces, although no sub-exponential time decoder is known. Our other approach involves recovering certain graph invariants, degree moments, that can identify a graphs degree sequence. Extremal polynomial bounds show that $\tilde Θ(n^{1/2})$ degree moments are necessary and sufficient to reconstruct the degree sequence, which leads to an algorithm with $\Exp{\tilde O(n^{1/2})}$ trace complexity. The same polynomial machinery yields a sub-exponential time decoder for the degree sequence from the moments. Additionally, we give an $O(n^{3})$ upper bound and a $Ω(n^2)$ lower bound for the trace complexity of recovering the number of edges.

Abstract: We study graph-based automata: nondeterministic finite automata obtained from edge-colored or oriented graphs by taking every vertex as both initial and accepting, and every edge as a pair of opposite transitions. The language of these automata corresponds to the set of edge-colored or oriented paths mapping to their corresponding graphs. We develop an analogous notion for trees and characterise the languages recognised by these models. For tree languages we prove the existence of a unique size- minimal graph and, more generally, a homomorphism-minimal graph for both word and tree languages using duality methods. In order to further motivate these models, we showcase a few results at the inter- section between graph theory and automata theory: We relate graph-based automata to reversible automata, give a decomposition of graph-based languages into reversible languages, and introduce the remanent language of an undirected graph as the inter- section of all its orientations. This remanent language captures structural information on the graph such as chromatic number.

Abstract: The directed clique number $\vecω(T)$ of a tournament $T$ is the minimum, over all orderings of the vertices of $T$, of the clique number of the graph whose edges are the arcs that point backward with respect to the ordering. In this paper, we prove that, for every integer $k \geq 3$, deciding whether $\vecω(T) \leq k$ is NP-complete. This answers a question of Nguyen, Scott, and Seymour, and contrasts with the classical undirected setting, where deciding whether $ω(G) \leq k$ is polynomial-time solvable for every fixed integer $k$. On the other hand, we give a polynomial-time algorithm distinguishing tournaments with $\vecω(T) \leq 2$ from those with $\vecω(T) > 100$. We also study the tournament analogue of the Gyárfás--Sumner conjecture. We construct new $\vecχ$-bounding tournaments and thereby prove a conjecture of Aboulker, Aubian, Charbit, and Lopes stating that every class of tournaments with bounded twin-width is $\vecχ$-bounded. We then exhibit new tournaments that are not $\vecχ$-bounding, disproving another conjecture of Aboulker, Aubian, Charbit, and Lopes, as well as two conjectures of Kim. Finally, we present infinite families of 3-$\vecω$-critical and 4-$\vecω$-critical tournaments.

Abstract: The cost of a hierarchical clustering can be represented by an ultrametric whose lowest-common-ancestor labels are cluster cardinalities. We relate this known representation to the shortest-path geometry of a similarity graph. For a connected support graph $G$, let $d_G$ be its unit-length shortest-path metric and let the edge weights enter only the objective. We prove that the shifted Dasgupta optimum is exactly the minimum edge-weighted cost of a cardinality-realizable ultrametric that dominates $d_G$. Connectedification lemmas put this problem and its freely labeled dominating-ultrametric relaxation on the same class of connected binary hierarchies, labeled respectively by cardinality and graph diameter. As a sharp baseline, we determine the exact worst-case price of cardinality realizability: on every $n$-vertex instance the ratio of the two optima is at most $(2n-1)/3$, with equality on the unweighted complete graph; the sharp factor for the standard unshifted objective is $2(n+1)/3$. Our principal structural result bounds this gap by a hereditary weighted fragmentation profile defined through connected balanced cuts. Uniform local control gives an $O(\log n)$ gap, polynomial decay gives a constant gap, and the logarithmic order is tight even for unweighted trees of maximum degree $3$. On locally regular bounded-degree trees, the hierarchy can be constructed in $O(n\log n)$ time. An energy decomposition and a geometric density bound provide supporting instance-sensitive estimates. Thus the cardinality label has an unavoidable linear worst case but admits substantially smaller bounds on natural sparse graph classes.