New graph kernels for evolving graphs with ordered neighborhoods.
problem Graphs with evolving edges over time.
method Combining convolutional subgraph kernels and string kernels, new scalable algorithms for generating graph feature maps.
result Neighborhood ordering yields more informative features.
Graph DNA uses Bloom filters to efficiently encode deep graph neighborhoods for better collaborative filtering.
problem Collaborative filtering struggles with exploiting deeper graph neighborhoods due to high time and space complexity.
method Graph DNA employs Bloom filters to compute approximate deep neighborhood information in linear time, enabling efficient encoding and utilization in collaborative filtering.
result Graph DNA significantly improves collaborative filtering performance with minimal computational and memory overhead.
An LSTM-based approach predicts graph nodes based on local neighborhood and node features.
problem Predicting graph nodes using local neighborhood and node features.
method Multi-level architecture based on LSTMs that learn to summarize neighborhoods from data.
result Effectiveness demonstrated on synthetic and real-world data.
MixHop learns complex neighborhood relationships in graphs.
problem Existing graph neural networks cannot learn certain neighborhood mixing relationships.
method MixHop repeatedly mixes feature representations of neighbors at various distances.
result MixHop outperforms on challenging baselines and visualizes neighborhood information prioritization.
GraphAIR improves graph representation learning by capturing non-linear interactions.
problem Challenges in capturing non-linear interactions in graph data.
method Integrates neighborhood aggregation and interaction modeling.
result Demonstrates improved performance on node classification and link prediction tasks.
NNK algorithm improves neighborhood and graph construction for machine learning.
problem Ad hoc selection of k and ε parameters in kNN and ε-neighborhood methods.
method NNK algorithm for better sparse signal approximation.
result NNK leads to superior performance in local neighborhood and graph-based machine learning tasks.
NEAR improves graph classification by aggregating edge information.
problem Loss of local structure and relationships in 1-hop neighborhood GNNs.
method Proposes NEAR, a framework that aggregates edge information between nodes in the neighborhood.
result NEAR improves graph classification tasks over existing 1-hop based GNN algorithms.
Revises GNN neighborhood aggregation for more accurate node classification.
problem Flaws in benchmark GNN models for node classification.
method Statistical signal processing approach to neighborhood aggregation.
result Novel insights for designing more efficient GNN models.
The k-NN graph has played a central role in increasingly popular data-driven techniques for various learning and vision tasks; yet, finding an efficient and effective way to construct k-NN graphs remains a challenge, especially for large-scale high-dimensional data. In this paper, we propose a new approach to const…
JK networks adapt to varying neighborhood sizes for better graph representation learning.
problem Fixed neighborhood aggregation limits model performance on graphs with diverse structures.
method Jumping Knowledge (JK) networks that use different neighborhood sizes for each node.
result JK networks achieve state-of-the-art performance on various graph datasets.
A neighborhood homotopy is an equivalence relation on spatial graphs which is generated by crossing changes on the same component and neighborhood equivalence. We give a complete classification of all 2-component spatial graphs up to neighborhood homotopy by the elementary divisor of a linking matrix with respect to th…
DNA improves graph neural networks by selectively aggregating node embeddings.
problem Static neighborhood aggregation limits graph neural networks' performance.
method Dynamic neighborhood aggregation guided by attention and controlled channel connections.
result DNA outperforms current methods in transductive node classification.
Neighborhood sampling affects graph neural network training outcomes.
problem Understanding the impact of neighborhood sampling on graph neural network training.
method Theoretical analysis using neural tangent kernels and Gaussian processes.
result Posterior covariance differs for different neighborhood sampling approaches, indicating no dominant approach.
A new GNN model SPIN achieves state-of-the-art performance on diverse real-world datasets.
problem Graph classification efficiency and accuracy.
method Parallel neighborhood aggregations (PA-GNNs) and SPIN model.
result SPIN model achieves state-of-the-art performance on diverse real-world datasets.
Proposes robust local scaling using conditional quantiles of graph similarities.
problem Spectral analysis sensitivity to parameters and noise.
method Auto-encoding neural network for inferring conditional quantiles of similarity functions.
result Proposed approach outperforms existing methods in spectral clustering and single-example label propagation.
Graph Denoising Policy Network learns robust representations from noisy graphs.
problem Noise sensitivity in graph representation learning.
method Reinforcement learning to select signal neighborhoods and aggregate features.
result Significantly outperforms state-of-the-art methods on node classification tasks.
GESF learns flexible graph node embeddings without specifying neighborhood or dependence.
problem Graph node embedding flexibility and neighborhood dependence specification.
method GESF uses set function technique to learn arbitrary representation functions from neighborhoods, automatically deciding neighbor significance.
result GESF outperforms state-of-the-art methods on graph classification tasks.
F-GCN improves graph convolutional networks for semi-supervised node classification.
problem Improving representation capacity of graph convolutional networks for multi-hop neighborhood information.
method Proposes a mathematically motivated, yet simple extension to existing GCNs.
result F-GCN outperforms state-of-the-art models on six out of eight datasets.
Develops GNNs for incomplete graphs, improving learning from missing node attributes.
problem Learning from incomplete graphs with missing node attributes.
method Introduces PaGNNs with novel partial aggregation functions for incomplete graph data.
result Demonstrates effectiveness and efficiency of PaGNNs on various datasets.
Spatial graphs study tangle replacement with equivalence classes.
problem Differentiating spatial graphs and their properties.
method Tangle replacement on spatial graphs, focusing on handcuff graphs.
result One-to-one correspondence between neighborhood equivalence classes and tangles.
Graph kernel uses Ricci curvature for comparison.
problem Graph comparison without node attributes.
method Edge curvature distribution for graph kernel.
result Graphs can be compared using topology alone.
DGCNN improves graph CNNs by handling irregular graphs.
problem Handling structural information loss and redundancy in graph CNNs.
method Proposes DGCNN using DGCL with mixed Gaussian model to handle irregular graphs.
result DGCNN outperforms state-of-the-art methods in graph classification and retrieval.
A new method encodes data structure from neighborhood-similarity graphs without bias.
problem Distortion and bias in high-dimensional data analysis.
method Directly encodes data point neighborhood similarities as a sparse graph, avoiding assumptions and iterative schemes.
result Efficacy demonstrated in natural and synthetic data applications.
GCNs improve regression tasks by aggregating neighbor signals.
problem GCNs' statistical properties in regression tasks are poorly understood.
method Examined two GCN convolutions and their impact on learning error.
result GCNs have a bias-variance trade-off that depends on neighborhood size and topology.
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.
Graphs with some negative Bakry-Émery curvature have explicit diameter bounds.
problem Understanding graphs with non-constant Bakry-Émery curvature.
method Proving distance bounds for graphs with positive Bakry-Émery curvature except for a finite or infinite set of non-positively curved vertices.
result Explicit upper bounds for the diameter of graphs with non-constant Bakry-Émery curvature.
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.
New method controls false edge detections in Gaussian graphical models.
problem High false edge detections in well-established estimators.
method Nodewise variable selection approach to control false discovery rate.
result Significant gain in performance compared to competing methods.
ES-MLP combines Graph-MLP with edge splitting for node classification on both homophilic and heterophilic graphs.
problem Node classification on graphs with mixed homophilic and heterophilic properties.
method Combines Graph-MLP with edge splitting mechanism from ES-GNN to learn two adjacency matrices based on relevant and irrelevant feature pairs.
result ES-MLP achieves performance comparable to homophilic and heterophilic models without using edges during inference.
IPGDN learns disentangled node representations in graphs.
problem Learning disentangled node representations in graph convolutional networks (GCNs).
method IPGDN uses neighborhood routing mechanism and HSIC to enforce independence among latent representations.
result IPGDN outperforms state-of-the-arts in graph classification, clustering, and visualization.
GCNs learn by embedding similar nodes within a class and leveraging consistent neighborhood structures.
problem Understanding how GCNs perform semi-supervised node classification on both homophilous and heterophilous graphs.
method Investigated the latent node embeddings and neighborhood structures of GCNs.
result GCNs learn by embedding similar nodes within a class and leveraging consistent neighborhood structures.
We study clustering algorithms based on neighborhood graphs on a random sample of data points. The question we ask is how such a graph should be constructed in order to obtain optimal clustering results. Which type of neighborhood graph should one choose, mutual k-nearest neighbor or symmetric k-nearest neighbor? What …
We prove the following estimate for the spectrum of the normalized Laplace operator Δ on a finite graph G, \begin{equation*}1- (1- k[t])^{\frac{1}{t}}\leq λ_1 \leq \cdots \leq λ_{N-1}\leq 1+ (1- k[t])^{\frac{1}{t}}, \,\forall \,\,\text{integers}\,\, t\geq 1. \end{equation*} Here k[t] is a lower bound for the Olli…
A new data-driven sampling method improves GraphSAGE's accuracy in node classification.
problem High variance in neighborhood sampling leads to sub-optimum accuracy in GraphSAGE.
method A data-driven node sampling approach using a non-linear regressor trained with reinforcement learning.
result Enhanced GraphSAGE accuracy in inductive node classification benchmarks.
Proposes a new method for predicting missing relations in knowledge graphs.
problem Predicting missing relations between entities in knowledge graphs.
method Relational message passing method considering only edge features without entity IDs.
result PathCon method outperforms state-of-the-art methods significantly.
SNG-DBSCAN clusters data faster with subsampled similarity queries.
problem Efficiently clustering large datasets with DBSCAN's high complexity.
method Subsampled ε-neighborhood graph for similarity queries. result Subsampling 0.1% of the graph leads to 200x speedup and 250x RAM reduction. Proposes BGCN-NRWS for semi-supervised node classification with reduced overfitting.
problem Uncertainty in graph structure for semi-supervised node classification.
method Bayesian Graph Convolutional Network using Neighborhood Random Walk Sampling (BGCN-NRWS) with MCMC graph sampling and variational inference.
result Consistently competitive classification results compared to state-of-the-art.
Structure learning in random fields has attracted considerable attention due to its difficulty and importance in areas such as remote sensing, computational biology, natural language processing, protein networks, and social network analysis. We consider the problem of estimating the probabilistic graph structure associ…
We introduce Graphical TREX (GTREX), a novel method for graph estimation in high-dimensional Gaussian graphical models. By conducting neighborhood selection with TREX, GTREX avoids tuning parameters and is adaptive to the graph topology. We compare GTREX with standard methods on a new simulation set-up that is designed…
Matching datasets of multiple modalities has become an important task in data analysis. Existing methods often rely on the embedding and transformation of each single modality without utilizing any correspondence information, which often results in sub-optimal matching performance. In this paper, we propose a nonlinear…
Flexible outlier detection using graph communities for robust performance.
problem Outlier detection in small sample size unbalanced problems.
method Local measure of label heterogeneity in a weighted graph topology.
result Overall outperforms local and global strategies in multi and single view settings.
DAGCN improves graph classification by learning neighbor importance and pooling.
problem Loss of early-stage information and loss of node characteristics in GCNs.
method Dual attention graph convolution and self-attention pooling.
result DAGCN outperforms state-of-the-art methods in graph classification.
Topology helps estimate chromatic numbers of random graphs on spheres.
problem Estimating chromatic numbers of random graphs on spheres.
method Topology, specifically connectivity of Lóvasz's neighborhood complex.
result Connectivity bound is useful in dimensions 1 and 2, but generally poor.
PGRec improves recommendation by modeling user-item preferences as a graph and embedding it for better predictions.
problem Sparse user-item data in recommender systems.
method PGRec models user-item preferences as a PrefGraph, then uses deep learning and factorization to embed and predict user preferences.
result PGRec outperforms state-of-the-art methods by up to 3.2% in NDCG@10.
Graph Attention Networks use masked self-attention to improve graph neural networks.
problem Improving graph neural networks to better handle graph data.
method Stacked masked self-attention layers that allow nodes to attend to their neighborhoods with different weights.
result GAT models achieve state-of-the-art results across various graph benchmarks.
A new graph neural network tackles oversmoothing and generalization issues.
problem Oversmoothing and poor generalization for unseen graphs in graph neural networks.
method Graph Entities with Step Mixture via random walk (GESM) that considers both edge-based and node-based features.
result GESM achieves state-of-the-art or comparable performances on benchmark datasets.
We propose a non-parametric link prediction algorithm for a sequence of graph snapshots over time. The model predicts links based on the features of its endpoints, as well as those of the local neighborhood around the endpoints. This allows for different types of neighborhoods in a graph, each with its own dynamics (e.…
Graph construction is a crucial step in spectral clustering (SC) and graph-based semi-supervised learning (SSL). Spectral methods applied on standard graphs such as full-RBF, ε-graphs and k-NN graphs can lead to poor performance in the presence of proximal and unbalanced data. This is because spectral methods based…