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.
New graph kernel scales well with graph size and number, achieving state-of-the-art performance.
problem Graph kernels lose structure information when representing graphs.
method Proposes a positive-definite global alignment graph kernel using random features and random graph embeddings.
result Achieves quasi-linear scalability with respect to graph size and number.
A fast graph embedding method for large graphs.
problem Efficiently embedding large graphs for various applications.
method One-hot graph encoder embedding with linear complexity.
result Graph encoder embedding is approximately normally distributed and converges to its mean.
Study on linking numbers in random book embeddings of complete graphs.
problem Distribution and mean of linking numbers in random book embeddings of complete graphs.
method Analyzes a family of two-component links arising from random embeddings of complete graphs, using Eulerian numbers and linear growth in mean linking number.
result Mean of squared linking number over all random embeddings is $ rac{i}{6}$, where i is the number of interior edges. Proposes a method to improve graph embedding by removing least frequent nodes.
problem Capturing global graph structure in random walk-based embeddings.
method Extends random walk-based graph embedding by removing least frequent nodes.
result Improves predictive performance slightly, if at all.
Paper explores embedding methods for detecting pseudo-cliques in random graphs, showing limitations and potential.
problem Detecting planted pseudo-cliques in random dot product graphs.
method Adjacency Spectral Embedding (ASE) and Graph Encoder Embedding (GEE).
result These methods can localize pseudo-cliques with additional clean network data, but not without it.
In order to model entanglements of polymers in a confined region, we consider the linking numbers and writhes of cycles in random linear embeddings of complete graphs in a cube. Our main results are that for a random linear embedding of Kn in a cube, the mean sum of squared linking numbers and the mean sum of square…
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.
The study analyzes convergence of random-walk embeddings in graph theory.
problem Understanding the convergence behavior of random-walk based vertex embeddings.
method Theoretical analysis of convergence in single and double limits of N and L. result Proved convergence of vertex embeddings under weak assumptions and derived concentration bounds.
Enhanced GNN with expanded attention window and partially random embeddings.
problem Limited expressivity of traditional GNNs in distinguishing non-isomorphic graphs.
method Graph attention network with expanding attention window and partially random initial embeddings. Head dropout for regularization.
result Improved ability to differentiate between non-isomorphic graphs.
New model preserves graph structure in large datasets.
problem Lack of permutation invariance in graph generation models for large graphs.
method Uses graph embeddings to create a scalable generative model.
result Model maintains structure in large graphs without losing invariance.
The paper examines how well node similarities are preserved by random projections in graph embeddings.
problem The preservation of node similarities under random projections in graph embeddings.
method Investigation of dot product and cosine similarity preservation by random projections over graph matrix rows.
result Random projections produce unreliable embeddings for dot product, especially for high-degree nodes.
The random graph is an infinite graph with the universal property that any embedding of G−v extends to an embedding of G, for any finite graph. In this paper we show that this graph embeds in the curve graph of a surface Σ if and only if Σ has infinite genus, showing that the curve system on an infinite genus s…
The random dot product graph (RDPG) is an independent-edge random graph that is analytically tractable and, simultaneously, either encompasses or can successfully approximate a wide range of random graphs, from relatively simple stochastic block models to complex latent position graphs. In this survey paper, we describ…
We present Graph Random Neural Features (GRNF), a novel embedding method from graph-structured data to real vectors based on a family of graph neural networks. The embedding naturally deals with graph isomorphism and preserves the metric structure of the graph domain, in probability. In addition to being an explicit em…
Network representation learning in low dimensional vector space has attracted considerable attention in both academic and industrial domains. Most real-world networks are dynamic with addition/deletion of nodes and edges. The existing graph embedding methods are designed for static networks and they cannot capture evol…
Study finds significant instability in node embeddings due to randomness.
problem Stability of node embeddings under random variations.
method Evaluated five node embedding algorithms (HOPE, LINE, node2vec, SDNE, GraphSAGE) on synthetic and empirical graphs.
result Significant instability in embedding spaces and downstream task accuracy.
Study shows gMPNNs struggle with OOD link prediction in larger test graphs.
problem Inductive out-of-distribution link prediction in larger test graphs.
method Theoretical analysis and development of a gMPNN with structural pairwise embeddings.
result Structural node embeddings from gMPNNs converge to random guessing as test graphs grow.
Extends random dot product graph model to handle multiple graphs.
problem Modeling and analyzing multiple graphs with shared nodes.
method Jointly embed adjacency matrices into a latent space.
result Node representations converge to latent positions with Gaussian error.
The paper introduces a new method for graph embedding using exponential family distributions.
problem Representing networks in a low dimensional latent space for various applications.
method Introduces the exponential family graph embedding model, generalizing random walk-based techniques to exponential family conditional distributions.
result The proposed techniques outperform existing methods in link prediction and node classification tasks.
RR-GCN uses random transformations instead of learned weights for node embeddings.
problem Learning node embeddings in KGs.
method Random Relational Graph Convolutional Network (RR-GCN) with untrained parameters.
result RR-GCN can compete with fully trained R-GCNs in node classification and link prediction.
DeepWalk embeddings converge on SBM graphs, recovering cluster structure.
problem Theoretical guarantees for DeepWalk embeddings on complex graphs.
method Solving a nonconvex optimization problem using random walks.
result DeepWalk embeddings on SBM graphs recover cluster structure with high probability.
Real-world data sets often provide multiple types of information about the same set of entities. This data is well represented by multi-view graphs, which consist of several distinct sets of edges over the same nodes. These can be used to analyze how entities interact from different viewpoints. Combining multiple views…
NodeSig efficiently computes binary node embeddings for scalable graph analysis.
problem Scalability issues in graph representation learning models.
method NodeSig uses random walk diffusion probabilities and stable random projections to compute binary node embeddings efficiently.
result NodeSig achieves a good balance between accuracy and efficiency on node classification and link prediction tasks.
Linear time algorithm for random walk kernels on sparse graphs.
problem Efficient computation of general random walk kernels for large graphs.
method Sample dependent random walks to compute graph embeddings without direct graph product.
result Up to 27x faster and scalable to 128x larger graphs than previous methods.
This work analyzes PPR-based node embeddings and their topological information.
problem Understanding and interpreting PPR-based node embeddings.
method Unified framework and two methods for topology recovery.
result PPR-based embeddings maintain more topological information than random walk-based embeddings.
The paper corrects for node degree in spectral clustering using random walk Laplacian.
problem Node degree heterogeneity in spectral clustering.
method Graph spectral embedding using the random walk Laplacian.
result The embedding provides uniformly consistent estimates of degree-corrected latent positions.
Graph embedding methods represent nodes in a continuous vector space, preserving information from the graph (e.g. by sampling random walks). There are many hyper-parameters to these methods (such as random walk length) which have to be manually tuned for every graph. In this paper, we replace random walk hyper-paramete…
Continuous vector representations of words and objects appear to carry surprisingly rich semantic content. In this paper, we advance both the conceptual and theoretical understanding of word embeddings in three ways. First, we ground embeddings in semantic spaces studied in cognitive-psychometric literature and introdu…
The paper introduces heterogeneous manifolds for better graph embeddings.
problem Graph embeddings in Euclidean spaces often fail to capture the curvature of real-world graphs.
method The authors propose heterogeneous rotationally-symmetric manifolds with a radial dimension to account for varying curvature.
result The method improves graph embeddings by better preserving high-order structures and heterogeneous random graphs.
Paper shows graphs can be embedded in lower dimensions than expected.
problem Choosing the right embedding dimension for graph analysis.
method Utilizes hidden manifold structure to predict lower-dimensional embedding.
result Graphs can be embedded in much lower dimensions than previously thought.
New method models aptamer libraries as Boltzmann-weighted graph ensembles for better affinity predictions.
problem Anomalous candidates in SELEX datasets obscure true aptamer-ligand affinity.
method Boltzmann graph ensemble embeddings for thermodynamically parameterized exponential-family random graphs.
result Proposed embedding enables robust community detection and subgraph-level explanations for aptamer ligand affinity.
ParPIC clusters directed graphs using random walks and diffusion operators.
problem Challenges in vertex-level clustering for directed graphs due to edge directionality.
method Parametrized Power-Iteration Clustering (ParPIC) based on reversible random walks and diffusion operators.
result ParPIC achieves competitive clustering accuracy with improved scalability compared to spectral and teleportation-based methods.
New graph embedding method improves link prediction and node classification.
problem Improving graph embedding methods for better node representation.
method Spectral-biased random walks with neighborhood similarity bias.
result Significantly improves link prediction and node classification.
A new method uses matrix sketches for efficient graph clustering in dynamic environments.
problem Efficiently clustering large, dynamic graphs in distributed memory systems.
method Inspired by spectral clustering, the approach uses random dimension-reducing projections to derive matrix sketches.
result The method produces embeddings that yield performant clustering results in a fully-dynamic stochastic block model stream.
New algorithms improve community detection and parameter estimation for PABM.
problem Improving community detection and parameter estimation for PABM.
method Connecting PABM to GRDPG, constructing new algorithms, and deriving asymptotic properties.
result Absolute number of community detection errors tends to zero as graph vertices increase.
GCNs distinguish graph models based on embeddings, but depth matters.
problem GCNs distinguish between different random graph models.
method Investigated the power of GCNs of varying depths to distinguish between graph models.
result GCNs with logarithmic depth can distinguish certain graphons, but simpler architectures suffice for others.
Node embeddings have become an ubiquitous technique for representing graph data in a low dimensional space. Graph autoencoders, as one of the widely adapted deep models, have been proposed to learn graph embeddings in an unsupervised way by minimizing the reconstruction error for the graph data. However, its reconstruc…
Feature extraction and dimension reduction for networks is critical in a wide variety of domains. Efficiently and accurately learning features for multiple graphs has important applications in statistical inference on graphs. We propose a method to jointly embed multiple undirected graphs. Given a set of graphs, the jo…
Random walks are at the heart of many existing network embedding methods. However, such algorithms have many limitations that arise from the use of random walks, e.g., the features resulting from these methods are unable to transfer to new nodes and graphs as they are tied to vertex identity. In this work, we introduce…
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.
The recent proliferation of publicly available graph-structured data has sparked an interest in machine learning algorithms for graph data. Since most traditional machine learning algorithms assume data to be tabular, embedding algorithms for mapping graph data to real-valued vector spaces has become an active area of …
SWAG uses graph convolutions to recommend products.
problem Product recommendation using graph-structured data.
method Graph Convolutional Network (GCN) with weighted random walks and aggregations.
result Graph-based approach improves product recommendations.
SASE improves attributed graph clustering for large graphs with linear time and space complexity.
problem Challenges in clustering large attributed graphs due to high computational and memory costs.
method SASE combines node features smoothing, scalable spectral clustering, and adaptive order selection.
result SASE achieves a 6.9% improvement in ACC and a 5.87x speedup on the ArXiv dataset.
The success of graph embeddings or node representation learning in a variety of downstream tasks, such as node classification, link prediction, and recommendation systems, has led to their popularity in recent years. Representation learning algorithms aim to preserve local and global network structure by identifying no…
We present a method to estimate block membership of nodes in a random graph generated by a stochastic blockmodel. We use an embedding procedure motivated by the random dot product graph model, a particular example of the latent position model. The embedding associates each node with a vector; these vectors are clustere…
The paper introduces a method for detecting principal communities and embedding vertices.
problem Detecting and embedding vertices in graphs with community structure.
method Principal graph encoder embedding method that detects principal communities and produces vertex embeddings.
result The method successfully detects principal communities and produces accurate vertex embeddings.
Vertex clustering in a stochastic blockmodel graph has wide applicability and has been the subject of extensive research. In thispaper, we provide a short proof that the adjacency spectral embedding can be used to obtain perfect clustering for the stochastic blockmodel and the degree-corrected stochastic blockmodel. We…