Graph neural networks struggle with counting certain substructures in graphs.
problem Detecting and counting specific substructures in graphs.
method Study of graph neural networks' ability to count attributed graph substructures.
result Graph neural networks like MPNNs, 2-WL, and 2-IGNs have limitations in counting certain substructures.
CNN estimates graphlet counts efficiently from historic graphs.
problem Difficulty in computing exact graphlet counts due to exponential growth.
method Convolutional Neural Network (CNN) framework with preprocessing techniques.
result Substantial speedup and high accuracy in estimating graphlet counts.
Paper tackles NP-complete subgraph isomorphism counting problem.
problem Counting subgraph isomorphisms in large graphs.
method Learning framework that augments representation learning architectures and iteratively attends pattern and target graphs.
result Scalable learning approach counts subgraph isomorphisms in linear time.
Enhances knot counting using mosaic diagrams.
problem Counting and classifying surface-links and knots.
method Marked graph diagrams and mosaic numbers.
result Established bounds on mosaic numbers for surface-links.
New bootstraps improve speed and accuracy for graph count functionals.
problem Efficiently counting subgraphs in large graphs.
method Developed two types of multiplier bootstraps: a fast, approximate linear one and a quadratic one for denser graphs.
result Both bootstraps provide valid inference and higher-order accuracy under different graph sparsity conditions.
Graphical estimation of count time series dependencies.
problem Estimating dependencies between multivariate count time series.
method Parameter-driven generalized linear model with l1-type regularization and MCEM algorithm.
result Characterization of disease spread interdependence and sources/sinks in Greater Mumbai.
Algorithm matches vertices of correlated Erdős-Rényi graphs efficiently.
problem Graph matching in correlated Erdős-Rényi graphs.
method Counting chandeliers to extract graph correlation.
result Correctly matches all but a vanishing fraction of vertices with high probability.
A new method for estimating graphlet counts in large networks.
problem Efficiently calculating graph statistics over massive networks.
method Lifting technique for Monte Carlo sampling of graphlets.
result Provable unbiasedness and controlled variance for all graphlets.
Counting tripods on a flat torus using lattice point counting.
problem Counting finite BPS webs in flat torus geometry.
method Lattice point counting techniques in C2. result Asymptotic counting result for tripods on the torus.
The family Blow Up formula is recalled. Certain combinatoric graphs are introduced for the discussion of the counting of nodal curves on an Kahler surface.
The paper develops formulas to count sizes of Markov equivalence classes of DAGs.
problem Measuring uncertainty and complexity in causal learning from DAGs.
method Introducing core graphs and deriving polynomial size formulas via symbolic computation.
result Efficient formulas for counting sizes of Markov equivalence classes of DAGs.
Graphs and local systems count multiwebs.
problem Counting multiwebs in graphs with local systems.
method Using Kasteleyn matrices and web-traces.
result Determinant of Kasteleyn matrix counts multiwebs.
Study geodesic paths on flat surfaces, comparing length and singularity counts.
problem Comparing geometric length and singularity counts on geodesic paths.
method Apply counting limit laws to infinite graphs and then to flat surfaces.
result Statistical comparison of geometric length and singularity counts on geodesic paths.
Introduces Niebrzydowski algebras for trivalent spatial graphs and handles.
problem Counting and distinguishing trivalent spatial graphs and handlebody-links.
method Defines Niebrzydowski algebras with ternary operation and partially defined multiplication, motivated by Reidemeister moves.
result Niebrzydowski algebras can distinguish some trivalent spatial graphs and handlebody-links.
Research connects prime numbers, graph theory, and cohomology.
problem Understanding the distribution of prime numbers using graph theory and cohomology.
method Discrete Morse-Smale complex and cohomology analysis.
result Explicit relationships between prime counting functions and cohomological properties of graphs.
The paper introduces a quantum state system to count perfect matchings in graphs.
problem Counting perfect matchings in graphs using quantum state systems.
method Topological quantum field theory (TQFT) and spectral sequences.
result The filtered n-color vertex homology for n=2 is generated by perfect matchings. This study compares GNNs and GA-MLPs, finding GA-MLPs can distinguish graphs but not count walks.
problem Comparing expressive power and graph isomorphism testing capabilities of GNNs and GA-MLPs.
method GA-MLPs augment node features with multi-hop operators and apply MLPs node-wise; GNNs are compared as a baseline.
result GA-MLPs can distinguish almost all non-isomorphic graphs but cannot count attributed walks, unlike GNNs.
Counting edge bicolorings of graphs on surfaces, with applications in knot theory.
problem Counting edge bicolorings of graphs on surfaces.
method Counting equivalence classes of edge bicolorings under specific relations.
result The equivalence classes of edge bicolorings on surfaces are computed, providing new insights.
Counting lattice points in moduli space of Klein surfaces.
problem Count lattice points in moduli space of Klein surfaces.
method Introduced metric Möbius graphs, counted lattice points weighted by non-orientability measure, deduced recursion for volumes.
result Proved refined version of Norbury's recursion and computed refined Euler characteristic.
New polynomials defined for quandle structures, enhancing graph invariants.
problem Enhancing the counting invariant for spatial graphs and handlebody-links.
method Introducing quandle polynomials and G-family polynomials for quandles, defining enhancements for invariants.
result New enhancements of the G-family counting invariant for trivalent spatial graphs and handlebody-links.
Study sub-tree counts in hyperbolic random geometric graphs.
problem Count sub-trees in hyperbolic graphs with varying curvature.
method Poisson point processes, hyperbolic metric, Palm calculus, Malliavin-Stein method.
result Phase transitions in sub-tree counts based on curvature and tree structure.
Counting periodic geodesics of bounded length and commutator structure on hyperbolic surfaces.
problem Counting periodic geodesics with specific commutator structure.
method Reduction to counting critical realizations of trivalent graphs.
result Asymptotic count of geodesics with bounded length and commutator structure.
New invariant counts graph configurations in 3D manifolds.
problem Counting graph configurations in 3D manifolds.
method Using combings instead of parallelizations for a more flexible definition.
result Universal finite type invariant of three-manifolds.
GraphMoE generates random graphs using neural networks and graphlets.
problem Learning generative models for random graphs.
method GraphMoE uses a neural network trained with graphlets and subgraph counts to match the distribution of random graphs.
result GraphMoE can generate graphs that mimic various real-world datasets and fool graph classifiers.
Paper describes a state sum formula for a graph coloring polynomial.
problem Counting n-face colorings of ribbon graphs for various n. method Combines topological quantum field theory and diagrammatic tensors.
result Describes a state sum formula for the total face color polynomial.
Generic loxodromic elements are common in hyperbolic groups and grow linearly.
problem Counting generic elements in hyperbolic groups.
method Combinatorial conditions on graph products and relatively hyperbolic groups.
result Loxodromic elements are common and have linear growth in translation length.
Graph Substructure Networks (GSN) improves GNN expressivity by counting subgraph isomorphisms.
problem Limited expressivity of GNNs in detecting and counting graph substructures.
method Topologically-aware message passing scheme based on substructure encoding.
result GSN is strictly more expressive than the Weisfeiler-Leman (WL) test and can disambiguate even hard graph isomorphism instances.
Counts and samples DAGs equivalent to a ground truth DAG.
problem Identifying the number and structure of DAGs equivalent to a ground truth DAG.
method Clique tree representation of chordal graphs for counting and sampling.
result Polynomial time algorithm for counting and sampling in bounded degree graphs.
Graph classification improved with motif counts and graphon theory.
problem Classifying large graphs with high accuracy.
method Using motif homomorphisms and graphon theory to provide bounds and a classifier.
result Explicit quantitative bounds for graph classification under noise.
Invariants from biquasile colorings distinguish surface-links.
problem Counting and distinguishing surface-links.
method Coloring oriented surface-links using biquasiles and marked graph diagrams.
result Invariants can distinguish closed surface-links and cobordisms.
Geometric Block Model improves community detection in sparse graphs.
problem Improving community detection in sparse graphs.
method Proposes a new geometric block model and a triangle-counting algorithm.
result Triangle-counting algorithm performs near-optimal in sparse graphs.
Efficient algorithm for graph matching in correlated stochastic block models.
problem Graph matching in correlated stochastic block models with balanced communities.
method Extends previous work on centered subgraph counts to handle estimation errors and edge correlation.
result First efficient algorithm for graph matching in the logarithmic average degree regime, matching all but a vanishing fraction of vertices with high probability.
Study links and quivers, proving polynomial equality conjecture.
problem Link and quiver invariants and their relations.
method Cluster algebra invariants, point count polynomials, skein relations.
result Equality conjecture between plabic graph link polynomial and quiver point count polynomial proved for specific cases.
Enhances knot counting invariant using biquasile Boltzmann weights.
problem Differentiating links with the same counting invariant.
method Introducing biquasile Boltzmann weights and identifying conditions for linear functions to be Boltzmann weights.
result Identifies proper enhancement of knot counting invariant.
A new test statistic counts tree co-occurrences to detect edge correlation between networks.
problem Detecting edge correlation between networks using latent vertex correspondence.
method The test statistic is based on counting co-occurrences of signed trees for a family of non-isomorphic trees.
result The test runs in n2+o(1) time and succeeds with high probability for large n. Geodesics count exponentially between triangulations of surfaces with enough topology.
problem Counting geodesics in triangulations of surfaces.
method Analyzing the flip-graph of triangulations and their geodesics.
result The number of geodesics grows exponentially for surfaces with enough topology.
Study counts and equidistributes geodesic orbits on curved spaces.
problem Counting and equidistribution of strongly reversible closed geodesics in negatively curved spaces.
method Generalized techniques from Sarnak and Erlandsson-Souto, thermodynamic formalism, and graphs of groups with 2-torsion.
result Asymptotic counting and equidistribution of geodesic orbits towards the Bowen-Margulis measure.
Study shows central limit theorem for counting measures in non-smooth spaces.
problem Counting measures in non-smooth spaces with coarse negative curvature.
method Established central limit theorems for actions of groups on hyperbolic spaces without properness or smoothness assumptions.
result General framework allows for applications in geometrically finite manifolds and intersection numbers.
GraphPrints detects anomalies in network flow data by analyzing graphlets.
problem Detecting anomalies in network flow data.
method Representing network flow as graphs, counting graphlets, and detecting outliers.
result Initial testing shows low false positive rates and high true positive rates.
Polynomial-time methods count and sample DAGs from equivalence classes.
problem Counting and sampling DAGs from Markov equivalence classes.
method Polynomial-time algorithms for DAGs.
result Counting and sampling can be done in polynomial time.
Proves quasimodularity of generating functions for torus covers.
problem Counting torus covers with and without Siegel-Veech weight.
method Analyzing decompositions of flat surfaces into horizontal cylinders, using quasi-elliptic functions.
result Quasimodularity arises as contour integral of quasi-elliptic functions.
R-GPM enables efficient graph pattern mining through user-defined relations.
problem Efficient graph pattern mining through user-defined relations.
method Parallel computing framework with MCMC sampling algorithm and optimizations.
result Efficient estimators for graph pattern statistics with up to 3-orders-of-magnitude computational cost reduction.
Proves quasimodularity of generating functions for pillowcase covers.
problem Counting Feynman-like graphs associated with quadratic differentials.
method Analyzing decompositions of half-translation surfaces into horizontal cylinders.
result Alternative proof of quasimodularity results and practical method to compute area Siegel-Veech constants.
The paper models crime risk using Foursquare check-ins and mobility data.
problem Understanding and predicting crime risk in urban areas.
method Directed graph of aggregated movement data, region risk factor derivation, DIFFER features.
result Reliable correlations between DIFFER features and crime count observed.
Multivariate count data are defined as the number of items of different categories issued from sampling within a population, which individuals are grouped into categories. The analysis of multivariate count data is a recurrent and crucial issue in numerous modelling problems, particularly in the fields of biology and e…
New maximally linkless graphs found with fewer edges.
problem Finding graphs without any links in 3D space.
method Demonstrated new maximally linkless graphs with improved edge count.
result Found maximally linkless graphs with m≤514n edges. Study uses knot theory to model RNA foldings, emphasizing both entanglement and intrachain interactions.
problem Modeling RNA foldings considering both entanglement and intrachain interactions.
method Combines knot theory with embedded rigid vertex graphs to emphasize both entanglement and intrachain interactions of RNA foldings.
result Defines and computes a coloring counting invariant for stuck links, providing explicit computations for arc diagrams of RNA foldings.
We find the minimal number of links in an embedding of any complete k-partite graph on 7 vertices (including K7, which has at least 21 links). We give either exact values or upper and lower bounds for the minimal number of links for all complete k-partite graphs on 8 vertices. We also look at larger complete bip…