Papers for

network analysis teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Hierarchical methods improve accuracy in autoregressive graph generation

Beyond Flat Walks: Compositional Abstraction for Autoregressive Graph Generation

Abstract: Autoregressive graph generators typically linearize graphs through flat node-edge walks, which can obscure higher-order structure in large and complex graphs. We introduce a hierarchical graph abstraction and coarse-to-fine generation pipeline that separates coarsening, tokenization, and decoding. This exposes three design axes: community coarsening, hierarchical tokenization, and order randomization. Across these axes, traversal-based hierarchy consistently improves distributional and structural fidelity, while its V.U.N.\ cost depends strongly on the coarsening and randomization policy. In particular, the fidelity--V.U.N.\ trade-off observed under within-community randomization is substantially reduced when traversal order is randomized across the full hierarchy. With a fixed backbone, training protocol, and matched training time across five molecular and five non-molecular benchmarks, hierarchical serialization yields consistent distributional and structural gains on all molecular datasets, while the non-molecular results further show that these gains depend on how well the supplied hierarchy aligns with structure in the target distribution. Together, these results characterize when and how hierarchical serialization benefits autoregressive graph generation.

Mon 9 NovMachine Learning
The gist
Generating graphs by listing their parts one by one can miss how parts fit together on a bigger scale. The authors found that grouping nodes into communities and creating a hierarchy before generating graphs can better capture these larger structures. This approach improves how closely generated graphs resemble real ones, especially when the hierarchy matches the graph’s natural organization. These improvements were shown consistently on chemical molecules and other graph datasets.
Open → 2611.12160v1

Regular path query results compressed drastically with tunnels technique

Tunnels: Compressing the Solution Subgraph of Regular Path Queries

Abstract: Regular path queries (RPQs) are increasingly expected to return the paths that match them, not only their endpoints. Since the number of matching paths can be exponential or infinite, a standard way to deliver them (PMR) is the subgraph $\Hs$ of the product between the graph and the query automaton that contains exactly the nodes lying on some solution path. We show that $\Hs$ can be compressed much further when the graph is available to the decoder: most of $\Hs$ can be regenerated by re-running small parts of the traversal, and only the places where the traversal would waste significant effort on dead branches need to be stored. We formalize this as \emph{tunnels}: regions of $\Hs$ that are re-expanded from a stored entry point with a bounded amount of extra work, either an absolute budget or one proportional to the output produced. We handle the three classes of RPQs: constant-to-variable, constant-to-constant, and variable-to-variable. In the latter, we study the combination of tunnels with cutting the query at a selective articulation point of the automaton and encoding the answer as a union of Cartesian products of leftward and rightward traversals. Our experimental results show improvements of 2 to 3 orders of magnitude over the baseline space of PMR, for an acceptable increase in traversal time.

Sat 7 NovData Structures and Algorithms
The gist
Some database questions ask for all paths that match a certain pattern, which can be extremely many or even infinite. The authors explore a way to shrink the data that describes all these paths, called the solution subgraph, by storing just parts needed and rebuilding the rest when needed through small reruns called tunnels. This method reduces the storage size a lot, by hundreds or thousands of times, while keeping the time to get answers reasonable. They test this on several kinds of queries and show it works well across different cases.
Open → 2611.10736v1

Optimal spectral gap bounds improve spin system simulations

Beyond the Bochner Method: Optimal Spectral Gaps for Block Dynamics of Spin Systems like the $O(N)$ Model

Abstract: Let $μ$ be a probability distribution on a spin system with $n$ sites and possibly infinite spin spaces. We prove local-to-global spectral-gap bounds for block Glauber dynamics. Given a symmetric, entrywise nonnegative matrix $A$ with zero diagonal and $λ_{\max}(A)<1$ encoding local spectral bounds for a spin system, we derive global spectral-gap bounds for block dynamics on its marginal distributions. These bounds are sharp: the Gaussian system with covariance $(I-A)^{-1}$ attains equality for every choice of disjoint blocks. Our proof extends the Bochner method through an abstract inequality for orthogonal projections on Hilbert spaces. As an application, we prove that Glauber dynamics for the $O(N)$ model, with $N\geq 2$, arbitrary external fields, and couplings of either sign, has spectral gap at least $(1-\|J_{\mathrm{abs}}\|_{\mathrm{op}}/N)/n$, where $J$ is the interaction matrix and $J_{\mathrm{abs}}=(|J_{ij}|)$. We also obtain spectral bounds for swap walks and local spectral expansion of partite simplicial complexes. For complexes formed from disjoint groups of ranks in random flags of subspaces over $\mathbb F_q$, we obtain a one-sided local spectral expansion bound of $2\sqrt q/(q+1)$. This bound is independent of the number and sizes of each group, and is nontrivial for every prime power $q$. Finally, for random forests $F$ of any finite graph with arbitrary positive edge weights, we prove that \[ \Pr(e,f\in F)\le \frac{4}{3} \Pr(e\in F)\Pr(f\in F) \] for distinct edges $e,f$, improving the factor 2 supplied by general log-concavity bounds for matroid independent sets. The argument combines our extended Bochner method with the analysis of an auxiliary real stable polynomial.

Tue 3 NovData Structures and Algorithms
The gist
The paper studies a way to measure how quickly certain random processes in physics and mathematics reach steady states. By improving a mathematical method called the Bochner method, the authors find more precise bounds for this speed in complex systems, including popular models like the O(N) model. Their work also gives new insights into related structures like random forests and simplicial complexes, helping understand interactions in networks and geometry. This helps computer simulations work better by knowing exactly how fast they mix.
Open → 2611.05228v1

Graph coarsening toolkit unifies methods and metrics for large graph analysis

GraCo: A Unified Toolkit of Graph Coarsening Algorithms and Metrics

Abstract: Graph coarsening aims to reduce a graph to a smaller one that preserves chosen properties of the original. It is increasingly used to scale graph learning to large graphs, as a non-differentiable step applied once before training. Many coarsening methods have been proposed in recent years, each with its own implementation, notation and evaluation. In this work, we introduce GraCo, a unified toolkit of graph coarsening methods. It relies on a single definition: a coarsening is fixed by a partition of the nodes and by the Laplacian the coarsened graph is consistent with. The coarsened graph, and the reduction and lifting matrices that map signals from the original graph to the coarsened one and back, follow from these two choices. We implement 17 methods from the literature and a random baseline, grouped into five families, with the same notation, inputs and outputs. We also build a collection of metrics from different papers, applicable to any coarsening. We check the implementations on a synthetic stochastic block model, then we report the runtime and peak memory of each method on Cora, PubMed, ogbn-arxiv and ogbn-products. GraCo is open-source and available at https://github.com/Antonin-J/graco.

Sat 31 OctMachine Learning
The gist
Working with very large networks can be slow and complicated. To tackle this, graph coarsening shrinks a big graph into a smaller one while keeping important features. The authors created GraCo, a toolkit that brings together many existing graph coarsening methods under one system, with a unified way to describe and evaluate them. This makes comparing and using these methods easier and more consistent for people who work with large graphs.
Open → 2611.01200v1

Topological deep learning tested on subtle shape properties beyond common features

Beyond Homology: Non-Abelian and Orientability Invariants Sensitivity in Cellular Networks

Abstract: Topological deep learning (TDL) architectures are typically evaluated on synthetic complex pairs that differ in a target invariant. Yet, whether a model recovers that invariant or an artifact of the chosen discretization is seldom audited. To examine this, we design and test pairs of complexes that look identical to standard homological and local message-passing tests, have the same Hasse graphs, yet differ in the target invariant. We study two beyond-homology regimes: nonAbelian fundamental-group structure and homotopy-matched orientability. For the former, we construct genus-2 pairs that match homology, cell statistics, local incidence profiles, and rank-colored Hasse 1-WL behavior while differing in their fundamental groups. For the latter, we evaluate punctured torus-Klein bottle pairs and show that distance, boundary, cycle, and spectral signals can confound apparent orientability detection, motivating stronger matched controls. Under the tested settings, subcomplex-lifted architectures separate some pairs beyond the matched homological, local-incidence, and Hasse 1-WL controls, while a depth sweep reveals an empirical depth-dependent trend without establishing a general barrier or direct computation of the target invariants. These results show that claims of topological expressivity must be stated relative to the model representation, explicitly controlled information channels, and the precise scope of the benchmark.

Thu 22 OctComputational Geometry
The gist
Topological deep learning models often check if they can recognize certain shape features, but it’s unclear if they truly understand these features or just pick up on accidental details. The authors created pairs of shapes that look the same by usual checks but differ in deeper, more complicated properties. They found that some models can distinguish these tricky differences, but only under specific conditions, and deeper investigation is needed to fully understand what the models learn. This means claims about these models’ abilities should be careful and precise about what they actually measure.
Open → 2610.31234v1

Quantum resource efficient Grover search methods improve vertex cover problem

Resource-Aware Grover Search for Minimum Vertex Cover

Abstract: The Minimum Vertex Cover (MVC) problem is a fundamental NP-hard combinatorial optimization problem with applications in network analysis and resource allocation. Grover's algorithm provides a quadratic reduction in query complexity for unstructured search, but existing Grover-based MVC formulations can incur substantial quantum resource overhead due to costly vertex-counting circuits and complex oracle constructions. We develop and evaluate several encoding and oracle-design strategies for reducing the qubit count, circuit depth, and gate complexity of Grover-based MVC search. First, we construct a Dicke-Parallel formulation that restricts the search to fixed-cardinality subsets, eliminating explicit vertex counting, together with a parallel edge-verification oracle that reduces feasibility-checking overhead. We then develop an Edge-Counting formulation that replaces per-edge auxiliary storage with a logarithmic-size counting register, substantially reducing ancillary-qubit requirements. Finally, we propose an Edge-Centric encoding that represents endpoint selections directly and derives vertex-selection states through incident-edge Boolean operations, enabling more depth-efficient oracle construction. Our resource analysis reveals complementary trade-offs among qubit width, circuit depth, gate count, and Grover iteration count. Edge-Counting is particularly attractive under tight qubit constraints, while Edge-Centric can reduce both circuit depth and Grover iteration count when the graph has a moderate edge count and sufficient representation multiplicity. Dicke-Parallel provides a more robust choice when such multiplicity is limited or graph density makes the edge-based search space large. These results provide practical guidance for selecting Grover-based MVC formulations according to hardware constraints and graph structure.

Mon 5 OctEmerging Technologies
The gist
Finding the smallest set of nodes that cover all edges in a network is a hard problem for computers. Grover's quantum search algorithm can speed this search but often requires lots of quantum resources, making it expensive. This paper explores new ways to design these quantum searches that use fewer qubits and simpler operations. The authors show trade-offs among different designs, helping to pick the best method depending on hardware limits and network structure.
Open → 2610.07252v1

Scalable method maintains dense groups in changing hypergraphs

Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance

Abstract: Hypergraphs model interactions involving groups of entities, and finding highly connected groups is a fundamental task in analyzing these data. When interactions arrive and expire, maintaining a dense group can require frequent and expensive changes to the underlying representation. We propose CAP, a scalable algorithm that explicitly maintains a $(1+ε)$-approximate densest subhypergraph under hyperedge insertions and deletions. The algorithm keeps a solution candidate together with an endpoint allocation that bounds the optimum density. The candidate's density guides maintenance: an update triggers repair only when this bound is too large to establish the required approximation. Local searches redistribute load or find a denser candidate, allowing CAP to retain useful solutions across many updates. We give an analysis that relates maintenance work to the size of the regions searched and the density lost by the maintained solution. It identifies conditions under which local repair remains inexpensive and provides a theoretical explanation for the observed efficiency. Experiments on real-world hypergraphs show speedups of up to nearly four orders of magnitude over the evaluated dynamic baselines, while supporting frequent queries and high accuracy. CAP also remains competitive with specialized dynamic graph methods on ordinary graphs, with speedups of up to approximately $64\times$ on the tested workloads.

Wed 30 SeptDatabases
The gist
Finding tightly connected groups in data that links many things at once can be very hard, especially when the connections keep changing. The authors created CAP, a fast and scalable method that keeps track of these dense groups even as connections are added or removed. It uses smart checks to only do work when necessary, making it much faster than previous methods. CAP also works well on simpler networks, not just complex hypergraphs.
Open → 2609.39778v1

Expressive power of implicit line-graph methods for graph comparison

On the Expressive Power of Implicit Line-Graph Higher-Order Weisfeiler--Leman

Abstract: Whitney's theorem allows isomorphism testing for connected simple graphs, apart from $K_3$ and $K_{1,3}$, to be formulated as distinguishing their line graphs. However, the relation between fixed-dimensional Weisfeiler--Leman (WL) expressivity on line graphs and on their roots remains unresolved. We study this relation through Implicit Line-Graph WL (ILG-$k$-WL), which is exactly $k$-WL on $L(G)$, executed over the edges of $G$ with line-graph relations derived from endpoint incidence and without explicitly constructing $L(G)$. On the Whitney-general class, the relation between root-domain and line-graph WL depends on $k$. For $k=1,2$, ILG-$k$-WL adds no distinguishing power beyond root-domain $1$-WL and misses some pairs that $1$-WL separates. For $k=3$, we prove the backward containment $L(G)\equiv_{3\text{-WL}}L(H)\Rightarrow G\equiv_{3\text{-WL}}H$. Strongly regular witness pairs, including the Shrikhande/rook pair, show that ILG-$3$-WL is strictly more expressive than $3$-WL. The backward containment also extends to disconnected graphs with no isolated vertices when every connected component is Whitney-general. Deterministic ILG-$3$-WL separates all three substructure-counting witness pairs, all $105$ pairs in SR25, and $359$ of $400$ BREC pairs. An untrained dense ILG-$3$-GNN gives the same pairwise verdicts on these evaluations.

Mon 14 SeptSocial and Information NetworksArtificial IntelligenceMachine Learning
The gist
Comparing complex networks to find out if they are essentially the same is an important problem. The authors study a way to compare graphs by looking at their edges and how those edges connect, without building an entire new graph explicitly. They show that this new method is at least as powerful as traditional methods in recognizing when two graphs are different and sometimes more so. Their approach works well on challenging example graphs and can be used to improve neural network models that analyze graphs.
Open → 2609.16412v1

ProtoGuide improves graph generation accuracy using prototype-driven guidance

ProtoGuide: Prototype-Driven Guidance for Class-Conditional Graph Generation

Abstract: Discrete diffusion models are a prominent family for graph generation, but standard class-conditional mechanisms embed the class signal in the denoiser during training, tying the conditioning mechanism to the trained model. Classifier guidance avoids this coupling in continuous domains by steering a frozen model with a classifier's gradient, but discrete graph diffusion samples discrete edge states, so gradients cannot propagate through the sampled graph. We introduce ProtoGuide, a post-hoc, backbone-agnostic framework that recovers an analogous mechanism. At each reverse step the denoiser's per-edge output is relaxed into a differentiable soft adjacency, embedded by a frozen Siamese graph neural network, and scored against a target-class prototype and its nearest competitor; the resulting per-edge gradient, damped by a cosine schedule, is injected back into the denoiser output. All components stay frozen, so guidance is retargeted by supplying a different prototype. On five classes of real-world networks and two architecturally different backbones, EDGE and DiGress, ProtoGuide raises macro classification accuracy from 50.7% to 73.5% and from 73.6% to 83.8%, and outperforms DiGress's built-in conditional training under our configuration. Gains are largest where the unguided models are weakest, and are not uniform across classes. Per-graph coverage remains high in most settings, while distributional effects are class-dependent. A Best-of-N selection baseline matches this accuracy given enough oversampling, but at a substantial cost in graph diversity. An independently initialized classifier, a directionality test, and a few-shot analysis support target-directed steering and robustness to very small support sets.

Mon 14 SeptMachine LearningArtificial Intelligence
The gist
Generating graphs with specific characteristics is hard because the usual ways of guiding the process don’t work well with discrete graph data. The authors developed ProtoGuide, which gently adjusts graph creation step-by-step by comparing parts of the graph to example patterns. This method can be applied to different existing graph generation models without retraining them and significantly improves their ability to create graphs matching desired classes. It works best where current methods struggle and keeps the generated graphs diverse and accurate.
Open → 2609.15239v1