The field of graph algorithms and network analysis is moving towards developing more efficient and scalable methods for handling large-scale graphs. Recent papers have focused on improving the performance of various graph algorithms, such as node labeling, graph edit distance, and vertex connectivity. Additionally, there is a growing interest in applying machine learning techniques to graph-related problems, including graph neural networks and unsupervised learning. Noteworthy papers include the development of a novel approach for computing graph edit distance via diffusion-based graph matching, which achieves superior solution quality and efficiency compared to existing methods. Another significant contribution is the proposal of a deterministic algorithm for computing vertex connectivity in near-linear time, breaking the long-standing time barrier. Overall, the field is witnessing significant innovations and advancements, driven by the increasing importance of graph-based models in various domains.
Advances in Graph Algorithms and Network Analysis
Sources
Fast online node labeling with graph subsampling
DiffGED: Computing Graph Edit Distance via Diffusion-based Graph Matching
Graph neural networks extrapolate out-of-distribution for shortest paths
The $g$-good-neighbor diagnosability of product networks under the PMC model
Multiplication of 0-1 matrices via clustering
A Tight Meta-theorem for LOCAL Certification of MSO$_2$ Properties within Bounded Treewidth Graphs
Can Invisible Psychological Traits Organize Visible Network Structure? A Complex Network Analysis of Myers-Briggs Type Indicator-Based Interaction Patterns in Anonymous Social Networks
Online Disjoint Spanning Trees and Polymatroid Bases
Unsupervised Learning for Quadratic Assignment
Finding Near-Optimal Maximum Set of Disjoint $k$-Cliques in Real-World Social Networks
Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
Adaptive Local Clustering over Attributed Graphs
Solving the Correlation Cluster LP in Sublinear Time
Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
Efficient Algorithms for Minimizing the Kirchhoff Index via Adding Edges
A Tolerant Independent Set Tester
A Local Perspective-based Model for Overlapping Community Detection
Fully dynamic biconnectivity in $\tilde{\mathcal{O}}(\log^2 n)$ time
Unsupervised Ordering for Maximum Clique
Randomized $\tilde{O}(m\sqrt{n})$ Bellman-Ford from Fineman and the Boilermakers