Graph-structured data arise ubiquitously in many application domains. A fundamental problem is to quantify their similarities. Graph kernels are often used for this purpose, which decompose graphs into substructures and compare these substructures. However, most of the existing graph kernels do not have the property of…
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,657 papers · 148 categories
Trend · papers per month
48 results for “Path Graphs”
We consider the problem of path inference: given a path prefix, i.e., a partially observed sequence of nodes in a graph, we want to predict which nodes are in the missing suffix. In particular, we focus on natural paths occurring as a by-product of the interaction of an agent with a network---a driver on the transporta…
In this thesis, we study the problem of feature learning on heterogeneous knowledge graphs. These features can be used to perform tasks such as link prediction, classification and clustering on graphs. Knowledge graphs provide rich semantics encoded in the edge and node types. Meta-paths consist of these types and abst…
PathNNs improve graph neural networks by distinguishing non-isomorphic graphs.
problem Limitations of standard GNNs in distinguishing non-isomorphic graphs.
method Proposes PathNNs that aggregate paths to update node representations.
result Two variants of PathNNs are strictly more powerful than 1-WL algorithm.
In this paper we use a time-evolving graph which consists of a sequence of graph snapshots over time to model many real-world networks. We study the path classification problem in a time-evolving graph, which has many applications in real-world scenarios, for example, predicting path failure in a telecommunication netw…
Convolution operations designed for graph-structured data usually utilize the graph Laplacian, which can be seen as message passing between the adjacent neighbors through a generic random walk. In this paper, we propose PAN, a new graph convolution framework that involves every path linking the message sender and recei…
PAN uses path integrals for graph convolution and pooling, improving GNN performance.
problem Designing efficient graph convolution and pooling for graph neural networks.
method Path integral based graph convolution and pooling using learnable weights for path lengths.
result PAN achieves state-of-the-art performance on various graph classification/regression tasks.
PathBoost boosts graph-level predictions using path-based features.
problem Graph-level classification and regression challenges.
method Gradient tree boosting method for graph-level prediction.
result PathBoost outperforms graph neural networks and graph kernel approaches in many cases.
Study on Frechet distance properties for paths and graphs.
problem Understanding topological properties of Frechet distance spaces.
method Proving path-connectedness of Frechet distance spaces and metric balls.
result Spaces of paths and graphs under Frechet distance are path-connected.
New method for learning on heterogeneous graphs without meta-paths.
problem Learning on heterogeneous graphs is sensitive to meta-paths choice, leading to poor performance.
method Decompose heterogeneous graph into homogeneous relation-type graphs, combine higher-order representations, use attention mechanisms.
result Our model outperforms state-of-the-art baselines in vertex classification tasks on heterogeneous graph datasets.
BWFlow improves graph generation by smoothly interpolating graph components.
problem Disjoint modeling of graph nodes and edges leads to irregular and non-smooth probability paths.
method Modeling graphs as MRFs and using optimal transport displacement for a smooth probability path.
result BWFlow achieves better training convergence and efficient sampling in graph generation.
Proposes a method to improve graph neural networks on heterogeneous graphs using meta-paths.
problem Improving graph neural networks on heterogeneous graphs with auxiliary tasks.
method Self-supervised auxiliary learning with meta-paths for heterogeneous graphs.
result Consistently improves link prediction and node classification on heterogeneous graphs.
Landmark-Based Node Representations for Shortest Path Distance Approximations in Random Graphsstat.ML
Landmark-based node embeddings approximate shortest path distances in random graphs.
problem Capturing global graph distances in node representations.
method Landmark-based node embeddings using shortest path distances from a subset of reference nodes (landmarks).
result Random graphs require lower dimensions in landmark-based embeddings compared to worst-case graphs.
Generative Flow Networks solve shortest path problems in graphs.
problem Finding shortest paths in graphs.
method Generative Flow Networks with flow regularization.
result Training a GFlowNet can solve pathfinding problems in arbitrary graphs.
We generalize to tree graphs obtained by connecting path graphs an oracle result obtained for the Fused Lasso over the path graph. Moreover we show that it is possible to substitute in the oracle inequality the minimum of the distances between jumps by their harmonic mean. In doing so we prove a lower bound on the comp…
Consider a weighted or unweighted k-nearest neighbor graph that has been built on n data points drawn randomly according to some density p on R^d. We study the convergence of the shortest path distance in such graphs as the sample size tends to infinity. We prove that for unweighted kNN graphs, this distance converges …
We describe unicorn paths in the arc graph and show that they form 1-slim triangles and are invariant under taking subpaths. We deduce that all arc graphs are 7-hyperbolic. Considering the same paths in the arc and curve graph, this also shows that all curve graphs are 17-hyperbolic, including closed surfaces.
A framework for hypothesis testing on attributed graphs using sampling.
problem Statistical testing on graph data, especially large attributed graphs.
method Sampling-based framework with PHASE and PHASEopt for accurate and efficient hypothesis testing.
result PHASE and PHASEopt improve accuracy and efficiency of hypothesis testing in attributed graphs.
Much of the recent work on learning molecular representations has been based on Graph Convolution Networks (GCN). These models rely on local aggregation operations and can therefore miss higher-order graph properties. To remedy this, we propose Path-Augmented Graph Transformer Networks (PAGTN) that are explicitly built…
Scalable machine learning with path signatures for time series and graphs.
problem Challenges in real-world time series and graph data.
method Combines rough path theory with probabilistic, deep, and kernel methods.
result Scalable models for time series and graph data.
The notion of friendliness between trees first appeared in solution of Lando's problem on intersection of polyhedra in 3-space. A tree is friendly to a path graph if edges of the tree can be numbered so that for each k,s the path between the edges k and k+1 contains either both or none of the edges k+2s,k+2s+1. Theorem…
Meta-graph is currently the most powerful tool for similarity search on heterogeneous information networks,where a meta-graph is a composition of meta-paths that captures the complex structural information. However, current relevance computing based on meta-graph only considers the complex structural information, but i…
ie-HGCN addresses HIN challenges by efficiently learning node representations.
problem Lack of flexibility in exploring meta-paths and high computational complexity in HIN GCN methods.
method Hierarchical aggregation architecture that automatically extracts useful meta-paths and reduces computational cost.
result ie-HGCN outperforms state-of-the-art methods on real network datasets.
Study proves hyperfiniteness of mapping class group actions on surface graphs.
problem Hyperfiniteness of mapping class group actions on surface graphs.
method Infinite unicorn paths and Gromov boundaries of arc and curve graphs.
result Proves hyperfiniteness of orbit equivalence relations induced by mapping class group actions.
A new graph kernel uses LCS and Wasserstein distance for better graph comparisons.
problem Graph learning methods can be limited by information from distant vertices and path length constraints.
method Proposes a Graph Kernel based on LCS similarity and Wasserstein distance in a novel metric space.
result The new kernel emphasizes comparisons between similar paths and reduces information loss.
Improved RL for knowledge graph reasoning with entity types.
problem Challenges in path-based relational reasoning over knowledge graphs.
method Type-enhanced RL agent using GNN for neighborhood information.
result Outperforms state-of-the-art RL methods and discovers novel paths.
We consider supervised learning problems where the features are embedded in a graph, such as gene expressions in a gene network. In this context, it is of much interest to automatically select a subgraph with few connected components; by exploiting prior knowledge, one can indeed improve the prediction performance or o…
We extend the notion of unicorn paths between two arcs introduced by Hensel, Przytycki and Webb to the case where we replace one arc with a geodesic asymptotic to a lamination. Using these paths, we give new proofs of the results of Klarreich and Schleimer identifying the Gromov boundaries of the curve graph and the ar…
The classical theorem of Fáry states that every planar graph can be represented by an embedding in which every edge is represented by a straight line segment. We consider generalizations of Fáry's theorem to surfaces equipped with Riemannian metrics. In this setting, we require that every edge is drawn as a shortest pa…
Developments in the theory of randomized shortest paths with a comparison of graph node distancesstat.ML
There have lately been several suggestions for parametrized distances on a graph that generalize the shortest path distance and the commute time or resistance distance. The need for developing such distances has risen from the observation that the above-mentioned common distances in many situations fail to take into ac…
Path queries on a knowledge graph can be used to answer compositional questions such as "What languages are spoken by people living in Lisbon?". However, knowledge graphs often have missing facts (edges) which disrupts path queries. Recent models for knowledge base completion impute missing facts by embedding knowledge…
A regularized optimization problem over a large unstructured graph is studied, where the regularization term is tied to the graph geometry. Typical regularization examples include the total variation and the Laplacian regularizations over the graph. When applying the proximal gradient algorithm to solve this problem, t…
EntroPath learns manifold geometry from diffusion paths.
problem Learning geodesic geometry from data graphs with spurious shortcuts.
method Maximum Entropy Path Ensemble Embedding (MERW) with k-step diffusion paths.
result EntroPath converges to squared geodesic distance in the short-time limit.
For a finite simplicial graph , let denote the right-angled Artin group on the complement graph of . In this article, we introduce the notions of "induced path lifting property" and "semi-induced path lifting property" for immersions between graphs, and obtain graph theoretical criteria for the embedabilit…
This work derives closed-form expressions computing the expectation of co-presence and of number of co-occurrences of nodes on paths sampled from a network according to general path weights (a bag of paths). The underlying idea is that two nodes are considered as similar when they often appear together on (preferably s…
The recently developed bag-of-paths (BoP) framework consists in setting a Gibbs-Boltzmann distribution on all feasible paths of a graph. This probability distribution favors short paths over long ones, with a free parameter (the temperature ) controlling the entropic level of the distribution. This formalism enables…
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.
Computing shortest path distances between nodes lies at the heart of many graph algorithms and applications. Traditional exact methods such as breadth-first-search (BFS) do not scale up to contemporary, rapidly evolving today's massive networks. Therefore, it is required to find approximation methods to enable scalable…
An efficient search-and-score algorithm for ancestral graphs using multivariate information scorescs.LG
Efficiently searches ancestral graphs using multivariate information.
problem Discovering causal relationships in graphs with latent variables.
method Greedy search-and-score algorithm with two-step approach.
result Outperforms existing methods on benchmark datasets.
Study shows saddle connection graph's geometry and quasi-isometry properties.
problem Characterize the geometry and quasi-isometry of saddle connection graphs.
method Proved 4-hyperbolicity and uniform quasi-isometry to a tree, used generalised unicorn paths.
result Saddle connection graph is not quasi-isometrically rigid and its boundary is straight foliations.
We present a simple, yet effective, approach to Semi-Supervised Learning. Our approach is based on estimating density-based distances (DBD) using a shortest path calculation on a graph. These Graph-DBD estimates can then be used in any distance-based supervised learning method, such as Nearest Neighbor methods and SVMs…
We show that the Hausdorff distance between any forward and any backward surgery paths in the sphere graph is at most 2. From this it follows that the Hausdorff distance between any two surgery paths with the same initial sphere system and same target sphere system is at most 4. Our proof relies on understanding how su…
Transformer adapts to graphs with adaptive attention and auto-regressive decoding.
problem Transformers struggle with graph data due to non-sequential nature.
method Proposes GRAT, a Transformer variant with adaptive attention and auto-regressive decoding.
result GRAT achieves state-of-the-art performance on molecule property predictions and generation tasks.
Guiding Graph Embeddings using Path-Ranking Methods for Error Detection innoisy Knowledge Graphscs.LG
Nowadays Knowledge Graphs constitute a mainstream approach for the representation of relational information on big heterogeneous data, however, they may contain a big amount of imputed noise when constructed automatically. To address this problem, different error detection methodologies have been proposed, mainly focus…
Improved bipartite link prediction using 2-hop paths.
problem Link prediction in bipartite networks without node attributes.
method Multiply reconstructed adjacency matrix with symmetrically normalized training adjacency matrix to form 2-hop paths.
result 2-hop paths improve link prediction performance.
Approximates cycles in planar and bounded-genus graphs.
problem Finding many disjoint cycles in planar and bounded-genus graphs.
method Constant-factor approximation algorithms for vertex-disjoint and edge-disjoint cycles.
result First algorithms for vertex-disjoint paths in fully planar and bounded-genus instances.
Efficient algorithms decide algebraic constraints of causal graphs.
problem Distinguish causal graphs with latent confounders.
method Study algebraic constraints and propose efficient algorithms.
result Decide equivalence or subset of algebraic constraints.
Geometric approach clusters intersecting manifolds with high probability.
problem Clustering intersecting d-dimensional manifolds.
method Compute locality graph on d-simplices using dihedral angles, then compute LAPD to separate manifold components.
result The method separates manifold components with high probability under random sampling.