A known failing of many popular random graph models is that the Aldous-Hoover Theorem guarantees these graphs are dense with probability one; that is, the number of edges grows quadratically with the number of nodes. This behavior is considered unrealistic in observed graphs. We define a notion of edge exchangeability …
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “exchangeable graph”
Directed graphs occur throughout statistical modeling of networks, and exchangeability is a natural assumption when the ordering of vertices does not matter. There is a deep structural theory for exchangeable undirected graphs, which extends to the directed case via measurable objects known as digraphons. Using digraph…
Many popular network models rely on the assumption of (vertex) exchangeability, in which the distribution of the graph is invariant to relabelings of the vertices. However, the Aldous-Hoover theorem guarantees that these graphs are dense or empty with probability one, whereas many real-world graphs are sparse. We prese…
Study uses graph techniques to understand meromorphic quadratic differential strata.
problem Understanding the topology of meromorphic quadratic differential strata.
method Exchange graph techniques to study fundamental groups; generalizes relations for mixed-angulations.
result Explicit presentations of fundamental groups in genus-zero case with four singularities.
It is assumed that under suitable economic and information-theoretic conditions, market exchange rates are free from arbitrage. Commodity markets in which trades occur over a complete graph are shown to be trivial. We therefore examine the vector space of no-arbitrage exchange rate ensembles over an arbitrary connected…
Graph learning improves FXRP and FXSA with significant statistical arbitrage gains.
problem Improving FXRP and FXSA with complex multi-currency and interest rate relationships.
method Two-step graph learning approach: first, edge-level regression on spatiotemporal graph; second, stochastic optimization with constraints and risk-adjusted return maximization.
result Graph-learning method achieves higher information and Sortino ratios than benchmarks.
We introduce the cluster exchange groupoid associated to a non-degenerate quiver with potential, as an enhancement of the cluster exchange graph. In the case that arises from an (unpunctured) marked surface, where the exchange graph is modelled on the graph of triangulations of the marked surface, we show that the univ…
We say that a graph is intrinsically knotted or completely 3-linked if every embedding of the graph into the 3-sphere contains a nontrivial knot or a 3-component link any of whose 2-component sublink is nonsplittable. We show that a graph obtained from the complete graph on seven vertices by a finite sequence of $\tria…
Interaction graphs, such as those recording emails between individuals or transactions between institutions, tend to be sparse yet structured, and often grow in an unbounded manner. Such behavior can be well-captured by structured, nonparametric edge-exchangeable graphs. However, such exchangeable models necessarily ig…
We study a simple exchange model in which price is fixed and the amount of a good transferred between actors depends only on the actors' respective budgets and the existence of a link between transacting actors. The model induces a simply-connected but possibly multi-component bipartite graph. A trading session on a fi…
We construct an infinitely exchangeable process on the set $\cate$ of subsets of the power set of the natural numbers via a Poisson point process with mean measure on the power set of . Each $E\in\cate$ has a least monotone cover in $\catf$, the collection of monotone subsets of $\cate$, an…
A new method for generating sets and graphs without requiring exchangeability.
problem Generating exchangeable distributions for sets and graphs is challenging.
method Top-n creation, a differentiable generation mechanism that selects relevant points from a latent vector.
result Top-n method outperforms i.i.d. generation in various tasks.
Conway-Gordon proved that for every spatial complete graph on 6 vertices, the sum of the linking numbers over all of the constituent 2-component links is congruent to 1 modulo 2, and for every spatial complete graph on 7 vertices, the sum of the Arf invariants over all of the Hamiltonian knots is also congruent to 1 mo…
New neural model processes 2D data with long-range dependencies efficiently.
problem Limited receptive field of convolutions for complex 2D tasks.
method Proposes Matrix Shuffle-Exchange network with layers and complexity.
result Exceeds convolutional and graph neural network baselines in long-range dependency modeling.
A Line Graph-Based Framework for Identifying Optimal Routing Paths in Decentralized Exchangesq-fin.CP
LG algorithm finds profitable trading paths in decentralized exchanges.
problem Identifying optimal trading paths in decentralized exchanges.
method Line-graph-based algorithm (LG) for efficient route discovery.
result LG consistently identifies more profitable paths than DFS with comparable costs.
Graphs from van der Corput sequence embed into Chamanara surface.
problem Embedding graphs from van der Corput sequence into surfaces.
method Constructed -regular graphs from van der Corput sequence and Kronecker sequence, embedded into torus and Chamanara surface.
result Graphs from van der Corput sequence embed into Chamanara surface with one edge removal.
This paper introduces cluster exchange groupoids for Coxeter-Dynkin diagrams and finds their fundamental groups are braid groups.
problem Understanding the fundamental groups of cluster exchange groupoids for Coxeter-Dynkin diagrams.
method Introduced cluster exchange groupoids for Coxeter-Dynkin diagrams and showed the fundamental group isomorphic to braid groups.
result The fundamental group of the exchange groupoid for a Coxeter-Dynkin diagram is the braid group associated with the diagram.
We consider the fully decentralized machine learning scenario where many users with personal datasets collaborate to learn models through local peer-to-peer exchanges, without a central coordinator. We propose to train personalized models that leverage a collaboration graph describing the relationships between user per…
Statistical network modeling has focused on representing the graph as a discrete structure, namely the adjacency matrix, and considering the exchangeability of this array. In such cases, the Aldous-Hoover representation theorem (Aldous, 1981;Hoover, 1979} applies and informs us that the graph is necessarily either dens…
Paper uses GNNs to efficiently detect profitable triangular arbitrage opportunities.
problem Detecting profitable triangular arbitrage opportunities in dynamic markets.
method Formulate the problem as a graph-based optimization task and use a GNN architecture to capture complex relationships.
result GNN-based method achieves higher average yield with reduced computational time compared to traditional methods.
A variety of machine learning tasks---e.g., matrix factorization, topic modelling, and feature allocation---can be viewed as learning the parameters of a probability distribution over bipartite graphs. Recently, a new class of models for networks, the sparse exchangeable graphs, have been introduced to resolve some imp…
The paper gives bounds for how long it takes for gossip protocols to spread information in networks.
problem Understanding the diffusion time in asynchronous gossip protocols.
method Provides non-asymptotic bounds for the number of messages needed for consensus in asynchronous gossip protocols.
result Explicit formula and approximation for the number of messages needed for consensus in different types of graphs.
Derives formulae for general permutation equivariant layers and presents a second order graph variational encoder.
problem Tackles the limitation of previous equivariant neural networks by considering permutations of matrices.
method Derives formulae for general permutation equivariant layers, including matrix permutations. Presents a second order graph variational encoder.
result Latent distribution of equivariant generative models must be exchangeable.
Paper detects anomalous edges in social networks using edge exchangeability.
problem Detecting anomalous edges in directed social networks.
method Exploits edge exchangeability and uses conformal prediction theory.
result Proposed anomaly detector has a guaranteed upper bound for false positives.
The cryptocurrency market is a very huge market without effective supervision. It is of great importance for investors and regulators to recognize whether there are market manipulation and its manipulation patterns. This paper proposes an approach to mine the transaction networks of exchanges for answering this questio…
We propose a novel statistical model for sparse networks with overlapping community structure. The model is based on representing the graph as an exchangeable point process, and naturally generalizes existing probabilistic models with overlapping block-structure to the sparse regime. Our construction builds on vectors …
Bayesian nonparametric approach for clustering non-exchangeable groups.
problem Clustering grouped data with dependencies among groups.
method Graphical Dirichlet process modeling with Markov property.
result Efficient posterior inference algorithm developed.
AP-GCN improves graph data processing by dynamically deciding communication steps.
problem Designing efficient and adaptive graph convolutional networks.
method Adaptive halting units that decide the number of communication steps at each node.
result AP-GCN achieves state-of-the-art results with minimal additional parameters.
CP-ROC bands improve graph classification accuracy and uncertainty quantification.
problem Uncertainty quantification and robustness to distributional shifts in graph classification.
method Conditional Prediction ROC (CP-ROC) bands for graph classification, developed for TGNNs and adaptable to GNNs.
result Statistically guaranteed coverage for CP-ROC under local exchangeability condition, improving prediction reliability.
Proposes a new method for completing swap cycles in decentralized exchanges.
problem Completing swap cycles in decentralized exchanges efficiently and without slippage.
method Introduces an asset matrix formulation to verify and complete CoW cycles using graph traversal and imbalance correction.
result Demonstrates efficient discovery and insertion of synthetic orders for atomic cycle closure.
New framework models non-exchangeable networks with latent orders and graphons.
problem Modeling non-exchangeable network data with complex dependencies.
method Latent orders and graphon-based approach for adjacency matrix probabilities.
result Consistent estimation and clustering of latent network structure.
New IPL graphs identified and conditions for their projective embeddings established.
problem Characterizing and identifying intrinsically projectively linked graphs.
method Applying Δ-Y exchanges and analyzing projective planar graphs.
result No minor-minimal IPL graphs on 16 edges exist, and new ones are identified.
Gradient flows on graphons converge to curves on graphon space.
problem Optimizing functions on large, exchangeable graphs.
method Euclidean gradient flow on edge weights converges to a curve on graphon space.
result Gradient flows on graphons can be described as curves of maximal slope on graphon space.
Kinetic models for wealth exchange on directed networksphysics.soc-ph
We propose some kinetic models of wealth exchange and investigate their behavior on directed networks though numerical simulations. We observe that network topology and directedness yields a variety of interesting features in these models. The nature of asset distribution in such directed networks show varied results, …
RoCP-GNN improves GNNs' robustness in graph node classification.
problem Uncertainty in GNN predictions for graph data.
method Integrates conformal prediction into GNN training for robust prediction sets.
result GNN models with size loss improve performance in node classification.
Mutation graph of support τ-tilting modules over skew-gentle algebras is connected.
problem Understanding the structure of support τ-tilting modules over skew-gentle algebras.
method Introducing mutation of maximal rigid objects and using exchange triangles to define mutations of support τ-tilting modules.
result The mutation graph of support τ-tilting modules over a skew-gentle algebra is connected.
A large collection of daily time series for 60 world currencies' exchange rates is considered. The correlation matrices are calculated and the corresponding Minimal Spanning Tree (MST) graphs are constructed for each of those currencies used as reference for the remaining ones. It is shown that multiplicity of the MST …
Study on communication delays in decentralized learning networks.
problem Optimizing communication latency in decentralized learning networks.
method Utilized network information theory and random geometric graph theory.
result Communication delay scales as O(n^(2-3β)/βlog n).
We use the correlation matrix of stocks returns in order to create maps of the São Paulo Stock Exchange (BM&F-Bovespa), Brazil's main stock exchange. The data reffer to the year 2010, and the correlations between stock returns lead to the construction of a minimum spanning tree and of asset graphs with a variety of thr…
The natural habitat of most Bayesian methods is data represented by exchangeable sequences of observations, for which de Finetti's theorem provides the theoretical foundation. Dirichlet process clustering, Gaussian process regression, and many other parametric and nonparametric Bayesian models fall within the remit of …
Correlation matrices of foreign exchange rate time series are investigated for 60 world currencies. Minimal Spanning Tree (MST) graphs for the gold, silver and platinum are presented. Inverse power like scaling is discussed for these graphs as well as for four distinct currency groups (major, liquid, less liquid and no…
Large Question-and-Answer (Q&A) platforms support diverse knowledge curation on the Web. While researchers have studied user behavior on the platforms in a variety of contexts, there is relatively little insight into important by-products of user behavior that also encode knowledge. Here, we analyze and model the macro…
This work generalizes graph neural networks (GNNs) beyond those based on the Weisfeiler-Lehman (WL) algorithm, graph Laplacians, and diffusions. Our approach, denoted Relational Pooling (RP), draws from the theory of finite partial exchangeability to provide a framework with maximal representation power for graphs. RP …
We propose a framework for the derivation and evaluation of distributed iterative algorithms for receiver cooperation in interference-limited wireless systems. Our approach views the processing within and collaboration between receivers as the solution to an inference problem in the probabilistic model of the whole sys…
Empirical evidence suggests that heavy-tailed degree distributions occurring in many real networks are well-approximated by power laws with exponents that may take values either less than and greater than two. Models based on various forms of exchangeability are able to capture power laws with , and admit tra…
The study examines convergence of stochastic processes on large graphs and adjacency matrices.
problem Analyzing convergence of stochastic processes on large graphs and adjacency matrices.
method Introduced new metrics on the space of measure-valued graphons and used them to show convergence of random trajectories to deterministic curves.
result The Metropolis chain converges to a deterministic gradient flow curve on the space of graphons under certain conditions.
New method embeds dynamic networks with stability for node behavior.
problem Embed time-evolving node representations with stability.
method Unfolded adjacency spectral embedding for dynamic networks.
result Method satisfies cross-sectional and longitudinal stability.
Exchangeable graphs arise via a sampling procedure from measurable functions known as graphons. A natural estimation problem is how well we can recover a graphon given a single graph sampled from it. One general framework for estimating a graphon uses step-functions obtained by partitioning the nodes of the graph accor…