We prove several results about chordal graphs and weighted chordal graphs by focusing on exposed edges. These are edges that are properly contained in a single maximal complete subgraph. This leads to a characterization of chordal graphs via deletions of a sequence of exposed edges from a complete graph. Most interesti…
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 “graph edge weights”
Node Embedding for Homophilous Graphs with ARGEW: Augmentation of Random walks by Graph Edge Weightscs.SI
ARGEW improves node embeddings for weighted homophilous graphs by emphasizing strong edge weights.
problem Lack of accurate node embeddings for weighted homophilous graphs.
method ARGEW (Augmentation of Random walks by Graph Edge Weights) augments random walks by emphasizing nodes with larger edge weights.
result ARGEW produces embeddings where node pairs with strong edge weights have closer embeddings.
Paper uses GNN and conformal prediction for accurate edge weight prediction.
problem Predicting edge weights on graphs for various applications.
method Graph Neural Network (GNN) with conformal prediction and error reweighting.
result Our method provides better coverage and efficiency than baselines.
Paper tackles dense subgraph discovery with noisy feedback.
problem Discover dense subgraphs in edge-weighted graphs with noisy feedback.
method Proposes polynomial-time and scalable algorithms for dense subgraph discovery.
result Polynomial-time algorithm obtains nearly-optimal solution with high probability.
Graph Neural Networks (GNNs) have been widely studied for graph data representation and learning. However, existing GNNs generally conduct context-aware learning on node feature representation only which usually ignores the learning of edge (weight) representation. In this paper, we propose a novel unified GNN model, n…
We introduce a principled method for the signed clustering problem, where the goal is to partition a graph whose edge weights take both positive and negative values, such that edges within the same cluster are mostly positive, while edges spanning across clusters are mostly negative. Our method relies on a graph-based …
Learning representation on graph plays a crucial role in numerous tasks of pattern recognition. Different from grid-shaped images/videos, on which local convolution kernels can be lattices, however, graphs are fully coordinate-free on vertices and edges. In this work, we propose a Gaussian-induced convolution (GIC) fra…
Flow on weighted graphs sharpens Bakry-Émery curvature.
problem Sharp curvature in weighted graphs.
method Bakry-Émery curvature flow on mixed weighted graphs.
result Limits of curvature flow are curvature sharp.
Graph convolutional networks (GCNs) are vulnerable to perturbations of the graph structure that are either random, or, adversarially designed. The perturbed links modify the graph neighborhoods, which critically affects the performance of GCNs in semi-supervised learning (SSL) tasks. Aiming at robustifying GCNs conditi…
Paper explores exact recovery of communities in weighted graphs using Gaussian and exponential distributions.
problem Exact recovery of communities in weighted graphs with Gaussian and exponential distributions.
method Introduces a new semi-metric to describe conditions for exact recovery and analyzes conditions for both complete and incomplete graphs.
result Necessary and sufficient conditions for exact recovery are asymptotically tight and applicable to both complete and incomplete graphs.
When analyzing weighted networks using spectral embedding, a judicious transformation of the edge weights may produce better results. To formalize this idea, we consider the asymptotic behavior of spectral embedding for different edge-weight representations, under a generic low rank model. We measure the quality of dif…
Paper introduces HGSL for heterogeneous graphs, improving edge type and weight recovery.
problem Learning structure in heterogeneous graphs with multiple node and edge types.
method Proposes H2MN model for DGPs and derives alternating optimization method.
result Demonstrates superior performance on synthetic and real-world datasets.
We consider the problem of learning the weighted edges of a balanced mixture of two undirected graphs from epidemic cascades. While mixture models are popular modeling tools, algorithmic development with rigorous guarantees has lagged. Graph mixtures are apparently no exception: until now, very little is known about wh…
Paper proposes an algorithm to reconstruct optimal model structure from graph adjacency matrix.
problem Optimal model structure reconstruction from weighted colored graph adjacency matrix.
method Uses prize-collecting Steiner tree algorithm to reconstruct minimum spanning tree.
result Demonstrates the effectiveness of the prize-collecting Steiner tree algorithm for model structure reconstruction.
Optimal Euclidean structure minimizes energy in weighted toroidal graphs.
problem Finding the optimal Euclidean structure for weighted toroidal graphs.
method Minimizing Dirichlet energy over all possible Euclidean structures and realizations within a fixed homotopy class.
result The optimal Euclidean structure induces a weighted Delaunay decomposition.
Graph attention improves node classification by distinguishing important edges.
problem Node classification in graph-based learning models.
method Theoretical analysis of graph attention networks for node classification.
result Graph attention can perfectly classify nodes in an 'easy' regime but fails in a 'hard' regime.
Graph Convolutional Networks (GCNs) have received increasing attention in the machine learning community for effectively leveraging both the content features of nodes and the linkage patterns across graphs in various applications. As real-world graphs are often incomplete and noisy, treating them as ground-truth inform…
A new kernel measures brain network similarities, improving disease classification.
problem Lack of edge weight information in existing graph kernels for brain connectivity networks.
method Ordinal pattern kernel for weighted brain connectivity networks.
result The ordinal pattern kernel achieves better classification performance than state-of-the-art graph kernels.
The (torsion) complexity of a finite edge-weighted graph is defined to be the order of the torsion subgroup of the abelian group presented by its Laplacian matrix. When G is d-periodic (i.e., G has a free action of the rank-d free abelian group by graph automorphisms, with finite quotient) the Mahler measure of its Lap…
A checkerboard graph of a special diagram of an oriented link is made a directed, edge-weighted graph in a natural way so that a principal minor of its Laplacian matrix is a Seifert matrix of the link. Doubling and weighting the edges of the graph produces a second Laplacian matrix such that a principal minor is an Ale…
Hypergraphs are used in machine learning to model higher-order relationships in data. While spectral methods for graphs are well-established, spectral theory for hypergraphs remains an active area of research. In this paper, we use random walks to develop a spectral theory for hypergraphs with edge-dependent vertex wei…
This paper proposes a method to learn graph representations by partitioning edges into communities.
problem Graph neural networks ignore how edges are formed, leading to suboptimal representation learning.
method Introduces a generative model to partition edges into community-specific weighted edges, then uses these for GNN-based inference and classification.
result The method learns discriminative representations for both node-level and graph-level classification tasks.
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.
BetaExplainer improves GNN interpretability by masking unimportant edges.
problem Interpreting GNNs' predictions is difficult due to black-box behavior and lack of uncertainty quantification.
method BetaExplainer uses a sparsity-inducing prior to mask unimportant edges during training.
result BetaExplainer provides uncertainty in edge importance and improves predictive accuracy on challenging datasets.
A distinguishing property of communities in networks is that cycles are more prevalent within communities than across communities. Thus, the detection of these communities may be aided through the incorporation of measures of the local "richness" of the cyclic structure. In this paper, we introduce renewal non-backtrac…
Study detects edge correlation between unlabeled random graphs.
problem Detect edge correlation between unlabeled random graphs.
method Hypothesis testing, conditional second-moment method, pseudoforest structure, enumeration of subpseudoforests.
result Sharp threshold for phase transition in testing error probability.
The paper predicts edge weights in weighted directed networks using metric geometry.
problem Predicting edge weights in weighted directed networks.
method Introducing new types of weighted directed networks (AWDNs), constructing metrics, and proposing modified kNN and SVM methods.
result The proposed methods outperform traditional approaches in predicting edge weights.
The paper proves ML estimators are strongly consistent for identifying edge weights in BAR models.
problem Identifying edge weights in Bernoulli Autoregressive (BAR) models.
method Maximum Likelihood (ML) estimation for two variants of BAR models.
result ML estimators are strongly consistent for edge weight identification.
The paper extends RDPG model to handle weighted graphs, enabling better analysis of network data.
problem Modeling networks with weighted edges to capture heterogeneous weight distributions.
method Proposes a nonparametric W-RDPG model with latent positions and moment-generating functions.
result Establishes statistical guarantees for estimating nodal latent positions and sampling graphs.
Functional connections in the brain are frequently represented by weighted networks, with nodes representing locations in the brain, and edges representing the strength of connectivity between these locations. One challenge in analyzing such data is that inference at the individual edge level is not particularly biolog…
This paper tackles matching two complete graphs with correlated edge weights in geometric models.
problem Matching two complete graphs with edge weights correlated through latent geometries.
method Derives an approximate maximum likelihood estimator for recovering hidden vertex correspondence.
result The estimator provably achieves perfect recovery under certain noise conditions.
DAGgr aggregates multiple DAGs to stabilize causal structure learning.
problem Stability in learning causal structure from data.
method Model averaging of candidate DAGs weighted by predictive likelihood, with acyclicity enforced.
result DAGgr consistently outperforms individual DAGs and bootstrap-aggregation baselines.
We generalize the stochastic block model to the important case in which edges are annotated with weights drawn from an exponential family distribution. This generalization introduces several technical difficulties for model estimation, which we solve using a Bayesian approach. We introduce a variational algorithm that …
Paper determines Assouad-Nagata dimension for all minor-closed metrics.
problem Understanding the Assouad-Nagata dimension of minor-closed metrics.
method Using edge-weighted graphs and edge-deletion/contraction to model minor-closed metrics, determining their Assouad-Nagata dimension.
result Determined the Assouad-Nagata dimension for every minor-closed metric.
In this paper we provide a principled approach to solve a transductive classification problem involving a similar graph (edges tend to connect nodes with same labels) and a dissimilar graph (edges tend to connect nodes with opposing labels). Most of the existing methods, e.g., Information Regularization (IR), Weighted …
Graph convolutional network (GCN) is generalization of convolutional neural network (CNN) to work with arbitrarily structured graphs. A binary adjacency matrix is commonly used in training a GCN. Recently, the attention mechanism allows the network to learn a dynamic and adaptive aggregation of the neighborhood. We pro…
This work improves graph inference using the degree-4 sum-of-squares hierarchy.
problem Recovering ground-truth binary labelings from corrupted edge observations.
method Apply the degree-4 sum-of-squares hierarchy to a quadratic combinatorial optimization problem.
result The solution of the dual problem is related to edge weights of Johnson and Kneser graphs.
We formulate weighted graph clustering as a prediction problem: given a subset of edge weights we analyze the ability of graph clustering to predict the remaining edge weights. This formulation enables practical and theoretical comparison of different approaches to graph clustering as well as comparison of graph cluste…
Study reconstructs hidden perfect matchings in random graphs with specific edge weights.
problem Reconstructing hidden perfect matchings in random weighted bipartite graphs.
method Analyzes the maximum likelihood estimator for matching reconstruction under different probability distributions of edge weights.
result Sharp threshold and infinite-order phase transition in reconstruction error for different probability distributions.
Alexander polynomial equals spanning tree count at t=1.
problem Alexander polynomial for spatial graphs.
method Combinatorial constructions generalized to weighted graphs.
result Value of Alexander polynomial at t=1 equals weighted spanning tree count.
Unified model combines GCN and LPA for better node classification.
problem Combining GCN and LPA for improved node classification.
method Unified model that unifies GCN and LPA, learns edge weights and attention weights.
result Unified model outperforms state-of-the-art GCN-based methods in node classification accuracy.
We analyze a new spectral graph matching algorithm, GRAph Matching by Pairwise eigen-Alignments (GRAMPA), for recovering the latent vertex correspondence between two unlabeled, edge-correlated weighted graphs. Extending the exact recovery guarantees established in the companion paper for Gaussian weights, in this work,…
RoGAT enhances GAT robustness against adversarial attacks.
problem Vulnerability of GAT to adversarial attacks.
method Dynamic adjustment of edge weights and features, with an extra attention score.
result RoGAT outperforms other defensive methods in robustness tests.
In the Network Inference problem, one seeks to recover the edges of an unknown graph from the observations of cascades propagating over this graph. In this paper, we approach this problem from the sparse recovery perspective. We introduce a general model of cascades, including the voter model and the independent cascad…
New method estimates Nishimori temperature for node classification in weighted graphs.
problem Estimating Nishimori temperature for Bayesian inference.
method Spectral method using eigenvalues of Bethe Hessian matrix.
result Spectral method outperforms existing approaches in node classification.
Dual-edge spatial Jacobian image graph for interpretable diabetic retinopathy grading
problem Automated diabetic retinopathy grading from color fundus photographs
method Dual-edge spatial-Jacobian image graph
result 0.8076 accuracy, 0.8312 quadratic weighted kappa, 0.5915 macro-F1, 0.9330 adjacent-grade accuracy
Recent advancements in deep neural networks for graph-structured data have led to state-of-the-art performance on recommender system benchmarks. In this work, we present a Graph Convolutional Network (GCN) algorithm SWAG (Sample Weight and AGgregate), which combines efficient random walks and graph convolutions on weig…
Model for material elasticity and plasticity using networks.
problem Understanding the elasticity and plasticity of materials.
method Developed a mathematical model based on networks, defining tension tensor for periodic graphs.
result The model explains elasticity and plasticity through local moves on graphs.