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.
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.
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.
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.
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.
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…
In graph neural networks (GNNs), pooling operators compute local summaries of input graphs to capture their global properties, and they are fundamental for building deep GNNs that learn hierarchical representations. In this work, we propose the Node Decimation Pooling (NDP), a pooling operator for GNNs that generates c…
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.
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. 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.
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.
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…
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.
We propose a novel graph pooling operation using cliques as the unit pool. As this approach is purely topological, rather than featural, it is more readily interpretable, a better analogue to image coarsening than filtering or pruning techniques, and entirely nonparametric. The operation is implemented within graph con…
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.
Graph embedding techniques have been increasingly deployed in a multitude of different applications that involve learning on non-Euclidean data. However, existing graph embedding models either fail to incorporate node attribute information during training or suffer from node attribute noise, which compromises the accur…
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.
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.
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.
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.
In rank aggregation (RA), a collection of preferences from different users are summarized into a total order under the assumption of homogeneity of users. Model misspecification in RA arises since the homogeneity assumption fails to be satisfied in the complex real-world situation. Existing robust RAs usually resort to…
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.
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…
Graph convolutional networks (GCNs) have been successfully applied in node classification tasks of network mining. However, most of these models based on neighborhood aggregation are usually shallow and lack the "graph pooling" mechanism, which prevents the model from obtaining adequate global information. In order to …
Electronic records contain sequences of events, some of which take place all at once in a single visit, and others that are dispersed over multiple visits, each with a different timestamp. We postulate that fine temporal detail, e.g., whether a series of blood tests are completed at once or in rapid succession should n…
Recent advances in representation learning on graphs, mainly leveraging graph convolutional networks, have brought a substantial improvement on many graph-based benchmark tasks. While novel approaches to learning node embeddings are highly suitable for node classification and link prediction, their application to graph…
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.
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).
With the advent of data science, the analysis of network or graph data has become a very timely research problem. A variety of recent works have been proposed to generalize neural networks to graphs, either from a spectral graph theory or a spatial perspective. The majority of these works however focus on adapting the …
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.
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.
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…
Graph classification receives a great deal of attention from the non-Euclidean machine learning community. Recent advances in graph coarsening have enabled the training of deeper networks and produced new state-of-the-art results in many benchmark tasks. We examine how these architectures train and find that performanc…
It is often hypothesized that a crucial role for recurrent connections in the brain is to constrain the set of possible response patterns, thereby shaping the neural code. This implies the existence of neural codes that cannot arise solely from feedforward processing. We set out to find such codes in the context of one…
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.