Large-scale graph analysis is computationally expensive, but many applications only need approximate results. How do different graph summarization methods compare across spectral, community, distance, and centrality tasks, and which approach works best for specific use cases?
- Benchmarked 3 paradigms (spectral sparsification, community collapse, spectral coarsening) on 4 web graphs up to 875K nodes / 7.6M edges evaluated on 5 fidelity metrics: spectral error, community NMI, average stretch, PageRank Precision@k, compression ratio
- Collapse minimized spectral error and path distortion at extreme compression (CompR ≈ 10⁻³ to 10⁻⁴), sparsifier was fastest (~6 to 27s summarize) and best at community retention (NMI up to 0.86), coarsening achieved top PageRank P@50 = 1.00 at moderate compression
- Provided task-driven guidance for choosing methods by metric and runtime budget; released modular code and reproducible protocol
Large language models require massive datasets for training, but not all data is equally valuable for downstream performance. How can we systematically identify and weight the most important training data to improve downstream task performance while reducing computational costs?
- Researched new pre-processing pipeline for categorizing text data into buckets that align with identified downstream tasks
- Investigated optimal data selection strategies for large language model training and developed importance weighting framework for pre-training data sampling to improve downstream performance
Recursive training on synthetic data triggers model collapse where diversity shrinks, tails vanish, and outputs degrade over generations. How can we design sampling schemes that keep synthetic text close to real-data distributions while preserving coherence and preventing model collapse?
- Compared 3 sampling regimes: baseline single-candidate, perplexity-based, and reference-proximity using embedding similarity to a held-out reference set
- Low-perplexity selection collapsed into spaces/punctuation; high-perplexity increased diversity but produced incoherent "gibberish", showing perplexity/log-prob are insufficient quality metrics
- Reference-proximity sampling yielded the smallest distribution shift in PCA of text embeddings and maintained coherence across generations (up to ~10)
Political polarization in Congress has increased dramatically, but traditional party affiliation metrics may miss nuanced voting patterns and cross-party collaboration. How can we model congressional voting behavior as networks to quantify bipartisanship and identify influential cross-party actors?
- Built binary and continuous similarity graphs from GovTrack roll calls; filtered to substantive bills and cleaned participation gaps
- Applied DCMM to estimate influence (θ) and mixed memberships (π) across party communities; achieved 98.9% party-alignment accuracy
- Identified moderate, cross-party actors (e.g., Rep. Brian Fitzpatrick (R), Rep. Henry Cuellar (D)) and linked bipartisanship with higher network influence in the binary model
Deferred acceptance (DA) algorithms guarantee stable matchings but inherently favor the proposing side, creating systematic unfairness. How do different stable matchings compare in terms of fairness and welfare, and how do preference correlation patterns affect these trade-offs?
- Built a simulation engine to enumerate stable matchings and construct the stable matching lattice; implemented 3 enumeration methods (naive, achievable-partner constrained, polytope vertex enumeration), observed ~10 to 13× speedups for the achievable method vs naive at n∈{8,10}
- DA extremes often maximize aggregate welfare for small n, but as n grows the welfare-maximizer shifts interior; the inequality-minimizer typically lies in the lattice interior
- L2 is more robust than L1; optimal points from L2 welfare/equality coincide more frequently than L1, penalizing "very bad for a few" outcomes
Multiple algorithms often make coupled decisions about the same person (e.g., banks and insurers both evaluating creditworthiness). When agents can strategically manipulate their features, this creates complex interactions between multiple decision-makers and strategic agents. How do strategic agents behave when facing multiple coupled decision rules, and what are the equilibrium outcomes when multiple learners simultaneously optimize their decision rules?
- Formalized a multi-learner strategic classification setting: learners simultaneously publish decision rules; a strategic agent chooses a manipulated report considering all rules and manipulation costs
- Characterized optimal responses for the agent x* and for each learner's best response bri under strictly concave utilities and linear manipulation cost
- Proved existence of PSNE among learners' released rules via continuity of argmax and Brouwer's Fixed-Point Theorem; parameters bounded over compact convex sets
Neural network training requires extensive hyperparameter tuning, but traditional sequential search methods are computationally expensive and time-consuming. How can we leverage parallel computing techniques to accelerate hyperparameter optimization while maintaining search quality and model performance?
- Devised approach combining openMP multi-threading and Asynchronous Successive Halving for optimal hyperparameter configurations
- Achieved 3.5x speedup over sequential baseline using single compute node, maintaining model flexibility while significantly reducing training time