BiGraphNet generalizes graph neural networks for more efficient operations.
problem Fragmented graph neural network architectures hinder optimization.
method Explicitly separates input and output nodes, enabling new efficient operations.
result BiGraphNet accelerates and scales computations in hierarchical networks.
This study improves graph coarsening methods by preserving graph spectrum and distances.
problem Solving large-scale graph problems by working on a smaller graph.
method Developed a geometric approach using Gromov--Wasserstein distance to minimize the difference between graph distances and their coarsened versions.
result Minimizing the difference between graph distances and their coarsened versions can be achieved using the weighted kernel K-means method. H-GCN enhances GCNs by pooling nodes to hyper-nodes for better global information.
problem Limited global information in shallow GCNs for semi-supervised node classification.
method Hierarchical graph pooling and refinement of coarsened graphs.
result H-GCN outperforms state-of-the-art methods on various graph datasets.
New graph coarsening method preserves GNN message-passing signals.
problem Preserving GNN message-passing on coarsened graphs.
method Proposed a new oriented message-passing operation for coarsened graphs.
result Improved node classification results compared to naive methods.
Sparse hierarchical graph classification improves graph-based benchmarks.
problem Sparse hierarchical graph classification challenges.
method Combining recent advances in graph neural network design, differentiable graph coarsening, and sparse pooling.
result Competitive hierarchical graph classification results possible without sacrificing sparsity.
Unified framework for graph coarsening using node features and graph matrices.
problem Dimensionality reduction of large graphs while preserving node features.
method Optimization-based framework that unifies graph learning and dimensionality reduction.
result The learned coarsened graph is ε-similar to the original graph, where ε is a small positive number.
Proposes clique pooling for graph classification.
problem Graph classification challenges.
method Clique-based graph pooling within GCN and GraphSAGE.
result Competitive performance on graph classification benchmarks.
Proposes GIC for graph convolution, improving graph classification.
problem Graphs lack local convolution kernels like images.
method GIC framework using edge-induced and vertex-induced Gaussian mixtures.
result GIC achieves state-of-the-art results on graph classification.
Efficiently computes embeddings for large graphs using coarsening.
problem Inefficient computation of graph embeddings for large-scale graphs.
method Graph coarsening based on Schur complements and Gaussian elimination.
result Efficiently computed embeddings on coarsened graph match Schur complement embeddings in expectation.
Paper introduces a taxonomy of reduction matrices for more efficient graph coarsening.
problem Efficiently reducing graph size while preserving important information.
method Introduces a more general notion of reduction matrix, not necessarily the pseudo-inverse of the lifting matrix.
result Reducing the Restricted Spectral Approximation (RSA) by modifying the reduction matrix.
Proposes SimPool for graph pooling using structural similarity features.
problem Challenges in graph pooling due to lack of spatial locality.
method Integrates structural similarity features with a revised pooling layer to propose SimPool.
result SimPool produces node cluster assignments resembling CNN's locality preserving pooling.
The paper introduces a pooling mechanism for graph CNNs using NMF.
problem Pooling in graph structured data for efficient computation.
method Non-negative matrix factorization for node pooling.
result The pooling mechanism improves graph classification performance.
A new unsupervised method learns graph hierarchies using optimal transport.
problem Learning meaningful graph hierarchies without labeled data.
method Differentiable coarsening and optimal transport.
result OTCoarsening produces meaningful coarse graphs and competitive performance.
How does coarsening affect the spectrum of a general graph? We provide conditions such that the principal eigenvalues and eigenspaces of a coarsened and original graph Laplacian matrices are close. The achieved approximation is shown to depend on standard graph-theoretic properties, such as the degree and eigenvalue di…
Paper improves GNN inference speed and memory usage.
problem Scalability issues in GNNs during inference.
method Graph coarsening techniques for faster inference.
result Significant reduction in inference time and memory usage.
New method reduces spatial graphs while preserving their topological features.
problem Finding a smaller spatial graph with the same structure.
method Topological spatial graph coarsening approach based on triangle-aware graph filtration.
result Significant reduction in graph size while preserving topological information.
A novel algorithm for unsupervised graph representation learning combining coarsening and mutual information maximization.
problem Current limitations in unsupervised graph representation learning, especially in embedding new graphs and considering both micro- and macro-structures.
method Combines coarsening with mutual information maximization to produce high-quality embeddings.
result The algorithm produces high-quality embeddings that are competitive with state-of-the-art methods.
Improved graph clustering with modularity and coarsening for attributes and communities.
problem Inaccurate community detection and computational inefficiency in graph clustering.
method Integrates coarsening and modularity maximization, using a loss function with log-determinant, smoothness, and modularity components.
result Superior clustering outcomes, proven consistent under DC-SBM, and efficient algorithm integration with GNNs and VGAEs.
PASCO speeds up graph clustering for large graphs.
problem Efficiently clustering large graphs with many communities.
method Overlay method combining coarsening and parallel clustering.
result PASCO accelerates clustering with improved efficiency and quality.
CoSimGNN improves graph similarity computation for large graphs.
problem Efficiently computing graph similarity scores for large graphs.
method Embedding-coarsening-matching framework with adaptive pooling and fine-grained interactions.
result CoSimGNN achieves best performance in graph similarity computation.
Graph Prolongation Convolutional Networks improve model performance in microtubule bending simulations.
problem Improving prediction accuracy in coarse-grained mechanochemical simulations of microtubule bending.
method Defines a novel ensemble Graph Convolutional Network model using optimized linear projection operators to map between graph scales.
result Graph Prolongation-Convolutional Network outperforms other GCN ensemble models in predicting microtubule bending potential energy.
NDP improves GNN efficiency by coarsening graphs without losing structure.
problem Efficiently summarize graph data for deep learning models.
method Node Decimation Pooling (NDP) reduces graph density while preserving topology.
result NDP achieves comparable performance to state-of-the-art pooling methods but with improved efficiency.
This work relaxes GNN symmetries to approximate automorphisms, improving model performance.
problem Improving graph neural network performance on asymmetric graphs.
method Formalizing approximate symmetries via graph coarsening, introducing a bias-variance formula.
result Best generalization performance achieved by choosing a larger symmetry group than automorphisms but smaller than permutations.
Study recovers community structure from coarse graph measurements.
problem Community recovery from low-resolution graph measurements.
method Formalized coarsening process of graph measurements, developed conditions for perfect recovery.
result Simple and closed-form asymptotic conditions for perfect recovery of coarse graph communities.
This thesis explores GNNs, categorizing them into local and global approaches.
problem Understanding the convergence of global GNNs and connecting local and global approaches.
method Categorization of GNNs into local and global, study of Invariant Graph Networks, connecting local and global approaches, and using local MPNN for graph coarsening.
result Established a connection between local and global GNN approaches.
GraphZoom improves graph embedding accuracy and scalability.
problem Node attribute noise and scalability issues in graph embedding models.
method GraphZoom combines graph fusion and multi-level coarsening to improve accuracy and scalability.
result GraphZoom significantly increases classification accuracy and speeds up the embedding process.
Efficient memory layer improves graph neural networks for graph classification and regression.
problem Efficiently learning node representations and graph coarsening for arbitrary graph topology.
method Introduces a memory layer for GNNs that learns node representations and graph coarsening, and two new networks: MemGNN and GMN.
result Proposed models achieve state-of-the-art results in graph classification and regression benchmarks.
ST-UNet models spatio-temporal graphs by pooling and unpooling operations.
problem Lack of effective means to extract dynamic features from spatio-temporal graphs.
method Designing a multi-scale architecture, Spatio-Temporal U-Net (ST-UNet), with paired sampling operations.
result Achieves substantial improvements in spatio-temporal prediction tasks.
iPool selects informative nodes for pooling in arbitrary graphs.
problem Pooling in graph neural networks is often overlooked.
method iPool uses a criterion based on neighborhood conditional entropy to select nodes for pooling.
result iPool achieves state-of-the-art performance on graph classification tasks.
MolHF generates complex molecules with hierarchical flow-based model.
problem Designing novel molecular structures with desired properties.
method MolHF is a hierarchical normalizing flow model that generates molecular graphs in a coarse-to-fine manner.
result MolHF achieves state-of-the-art performance in random generation and property optimization.
Study intersection homotopy groups in coarsenings of CS sets.
problem Understanding invariance of intersection homotopy groups in coarsenings of CS sets.
method Introduced a general perversity and its pushforward, established invariance theorems for intersection homotopy groups in coarsenings of CS sets.
result Found invariance theorems for intersection homotopy groups in coarsenings of CS sets.
Can one reduce the size of a graph without significantly altering its basic properties? The graph reduction problem is hereby approached from the perspective of restricted spectral approximation, a modification of the spectral similarity measure used for graph sparsification. This choice is motivated by the observation…
Graph classification models are sensitive to initialisation and structure, but simple models perform well.
problem Graph classification models' performance is sensitive to initialisation and structure.
method Examined recent graph coarsening architectures and their performance sensitivity.
result Simple models like MLP, single-layer GCN, and fixed-weight GCN achieve competitive performance.
New estimators improve efficiency in two-phase designs with coarsened data.
problem Efficient estimation in two-phase designs with incomplete data.
method Developed new estimators within the TMLE framework.
result New estimators are asymptotically equivalent and more efficient.
We consider the problem of statistical inference for ranking data, specifically rank aggregation, under the assumption that samples are incomplete in the sense of not comprising all choice alternatives. In contrast to most existing methods, we explicitly model the process of turning a full ranking into an incomplete on…
Paper improves graph convolutional networks by adjusting filter size.
problem Improving predictive performance of graph convolutional networks.
method Introducing a hyper-parameter to influence filter size in graph convolutions.
result Improves predictive performance of Deep Graph Convolutional Networks.
Adaptive graph convolution improves attributed graph clustering performance.
problem Joint modeling of graph structures and node attributes is challenging.
method Adaptive graph convolution that captures global cluster structure and selects appropriate order for different graphs.
result Empirical results show our method compares favorably with state-of-the-art methods.
Spectral graph convolutional neural networks (CNNs) require approximation to the convolution to alleviate the computational complexity, resulting in performance loss. This paper proposes the topology adaptive graph convolutional network (TAGCN), a novel graph convolutional network defined in the vertex domain. We provi…
Recently, graph neural networks (GNNs) have revolutionized the field of graph representation learning through effectively learned node embeddings, and achieved state-of-the-art results in tasks such as node classification and link prediction. However, current GNN methods are inherently flat and do not learn hierarchica…
In this work we propose a simple and easily parallelizable algorithm for multiway graph partitioning. The algorithm alternates between three basic components: diffusing seed vertices over the graph, thresholding the diffused seeds, and then randomly reseeding the thresholded clusters. We demonstrate experimentally that…
GRASPEL learns large graphs from data efficiently.
problem Learning meaningful graphs from data for various applications.
method Highly scalable spectral approach using graph Laplacians and coarsening techniques.
result Ultra-sparse graphs with improved efficiency and accuracy in spectral clustering and t-SNE.
Graph convolutional Gaussian processes learn functions on graphs.
problem Learning translation-invariant relationships on non-Euclidean domains.
method Bayesian nonparametric method using graph convolutional neural networks.
result Graph convolutional Gaussian processes outperform existing methods on images and triangular meshes.
This paper introduces Haar convolution for GNNs to reduce computational cost.
problem High computational cost in GNNs for large graph sizes.
method Introduces Haar basis for graph convolution and Fast Haar Transforms.
result State-of-the-art results on graph-based regression and node classification tasks.
Graph convolutional kernel networks generalize CNNs to graph data.
problem Representing graph-structured data for machine learning.
method Convolutional kernel networks applied to graph data.
result Competitive performance on graph classification benchmarks.
This paper develops a coreset method for GNNs that speeds up training on large graphs.
problem Training Graph Neural Networks (GNNs) on large-scale graphs is computationally expensive.
method The paper proposes a spectral greedy coreset (SGGC) method that selects ego-graphs based on spectral embeddings.
result SGGC significantly speeds up GNN training on large graphs and outperforms other coreset methods.
Develops BASGCN for graph classification with improved feature learning.
problem Graph classification with information loss and imprecise representation.
method Transforms graphs into grid structures and defines a new spatial graph convolution operation.
result Reduces information loss and improves feature representation compared to existing models.
New method for valid prediction intervals with coarsened data.
problem Handling missing data and censored outcomes in training samples.
method Multiply robust conformal risk control with semiparametric theory.
result Stronger coverage properties under covariate shift.
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.