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.
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.
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.
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.
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.
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…
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. 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.
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 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…
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.
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.
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.
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.
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.
Paper uses Shapley values to identify key confounders in product funnel data.
problem Identifying important confounders in product funnel data.
method Applies Shapley values for scalable coarsened exact matching.
result Shapley values provide robust importance-ranking for confounders.
New methods for handling confounding in observational studies.
problem Handling confounding variables in observational studies.
method Generalized coarsened procedures for clustering confounding variables, followed by estimation of treatment effects and variance.
result Developed a general asymptotic framework for the average causal effect estimator and variance formulae.
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.
New algorithm tackles self-selection bias in estimating linear regressors.
problem Estimating k linear regressors with self-selection bias in d dimensions. method First local convergence algorithm for self-selection, reducing to coarsening problem.
result Improves running time of previous algorithms by a poly(d, k, 1/ε) factor.
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.
Paper creates transparent, safe synthetic data from coarsened margins.
problem Creating synthetic data that maintains original relationships and is safe from disclosure.
method Defining and curating margins, applying SDC, coarsening counts, and using IPF algorithm.
result Synthetic data derived from safe, coarsened margins maintains original relationships.
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…
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.
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.
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.
New framework estimates target functions from incomplete data.
problem Estimating target functions from partially observed data.
method IF-learning framework using influence functions.
result Two learning algorithms developed for estimation.
New method reduces confidence interval sizes for causal inference.
problem Inaccurate propensity scores and extreme scores cause large confidence intervals.
method Data-dependent Coarse IPW (CIPW) estimators.
result Robust CIPW estimators reduce confidence interval sizes to ε+1/√n.
Develops combinatorial theory of vector bundles on simplicial complexes.
problem Creating a discrete theory for vector bundles and connections on simplicial complexes.
method Introduces discrete exterior covariant derivative and applies it to various geometric objects.
result Flat discrete connections yield a cochain complex computing twisted de Rham cohomology.
Dynamical systems with large state-spaces are often expensive to thoroughly explore experimentally. Coarse-graining methods aim to define simpler systems which are more amenable to analysis and exploration; most current methods, however, focus on a priori state aggregation based on similarities in transition rates, whi…
CoarsenRank improves robustness in rank aggregation despite model misspecification.
problem Rank aggregation under model misspecification in real-world scenarios.
method CoarsenRank designs a neighborhood of ideal preferences to handle agnostic noise-corrupted data.
result CoarsenRank achieves robustness against model misspecification within a defined neighborhood.
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.
New method reduces bias in estimating causal effects from discretized variables.
problem Bias in estimating causal effects from discretized continuous variables.
method Proposes a bias-reduced functional that evaluates outcome regression at within-bin conditional means.
result Demonstrates substantial bias reduction and near-nominal confidence interval coverage.
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.
Proposes models to analyze irregular healthcare time series data.
problem Irregular timestamps in healthcare time series data.
method Data augmentation, temporal coarsening, MultiResolution Ensemble (MRE) model.
result Improves mAP on mortality prediction task from 51.53% to 53.92%.
Generative models synthesize microstructures respecting physical invariances.
problem Synthesizing microstructures given limited images and physical constraints.
method Three generative models: WGAN, physics-informed GAN, and hybrid model.
result Synthesized microstructures respect physical invariances and latent variable constraints.
In sequential anytime-valid inference, any admissible procedure must be based on e-processes: generalizations of test martingales that quantify the accumulated evidence against a composite null hypothesis at any stopping time. This paper proposes a method for combining e-processes constructed in different filtrations b…
Predicts fine-grained OD matrices for ridesharing platforms to optimize supply-demand balance.
problem Accurately predicting spatial-temporal OD demands for ridesharing platforms.
method OD-CED model combining unsupervised space coarsening and encoder-decoder architecture.
result Significant improvement in prediction accuracy (45% RMSE reduction, 60% WAPE reduction).
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.
Current state-of-the-art discrete optimization methods struggle behind when it comes to challenging contrast-enhancing discrete energies (i.e., favoring different labels for neighboring variables). This work suggests a multiscale approach for these challenging problems. Deriving an algebraic representation allows us to…
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.
Suppose C is a compact, n-edged two-cell of the centered dual decomposition of a locally finite set in the hyperbolic plane, a coarsening of the Delaunay tessellation which was introduced in the author's prior work. We describe an effectively computable lower bound on the area of C, given an n-tuple of positive…
We give sharp upper bounds on the maximal injectivity radius of finite-area hyperbolic surfaces and use them, for each g at least 2, to identify a constant r_{g-1,2} with the property that the set of closed genus-g hyperbolic surfaces with maximal injectivity radius at least r is compact if and only if r > r_{g-1,2}. T…
Transformers approximate Bayesian posteriors but not exactly.
problem Bayesian accounts of in-context learning face challenges due to task-preserving order changes in transformers.
method Showed that excess prequential code length is exactly cumulative predictive KL, decomposing expected regret into order-averaged predictor and order-averaging gain.
result Transformers approximate Bayesian posteriors but not exactly, priced by log loss.