Characterizes graphs with Lin-Lu-Yau curvature at least one and explores bone-idle graphs.
problem Characterizing graphs with specific curvature properties.
method Study of Ollivier-Ricci curvature and Lin-Lu-Yau curvature, exploration of regular graphs, and exact formula derivation.
result Characterizes edges that are bone-idle in regular graphs and provides a complete characterization of 4-regular bone-idle graphs.
Curvature formulas on regular graphs identified bone idle edges and graphs.
problem Understanding curvature in regular graphs and identifying bone idle edges.
method Explicit formulas for Lin-Lu-Yau and Ollivier-Ricci curvatures derived from graph parameters.
result Equality condition on regular graphs for Ollivier-Ricci curvature and characterization of bone idle edges.
Sharp bounds on diameter and eigenvalues for amply regular graphs.
problem Finding bounds for amply regular graphs' diameter and eigenvalues.
method New ideas relating discrete Ricci curvature to local matching properties, including a novel construction of a regular bipartite graph.
result Sharp diameter and eigenvalue bounds for amply regular graphs.
Propagation-regularization improves GNN performance by infusing extra graph information.
problem The effectiveness of graph Laplacian regularization in GNNs is questioned and improved upon.
method Introducing Propagation-regularization (P-reg) to enhance GNN performance.
result P-reg boosts GNN performance on various tasks across multiple datasets.
The paper proves diameter bounds and finiteness for amply regular graphs.
problem Proving diameter bounds and finiteness for amply regular graphs.
method Improved curvature estimates and new Bakry-Émery curvature estimates.
result There are only finitely many amply regular graphs with specific parameters.
This paper uses the relationship between graph conductance and spectral clustering to study (i) the failures of spectral clustering and (ii) the benefits of regularization. The explanation is simple. Sparse and stochastic graphs create a lot of small trees that are connected to the core of the graph by only one edge. G…
We embed arbitrary groups into regular graphs with prescribed automorphisms.
problem Embedding arbitrary groups into regular graphs with specific automorphisms.
method Constructing regular graphs with strong embeddings and automorphism groups isomorphic to any given finite group.
result For every d≥3 and every finite group G, there exists a d-regular graph Γ with a strong embedding β such that Aut(Γ)≅Aut(β(Γ))≅G. Study on Lin-Lu-Yau curvature and diameter of amply regular graphs.
problem Lower bounds of Lin-Lu-Yau curvature in amply regular graphs.
method Application of Hall's marriage theorem and geometric proof.
result Conference graphs have positive Lin-Lu-Yau curvature.
The study shows that certain graphs are regular at boundary points.
problem Boundary regularity of anisotropic minimal Lipschitz graphs.
method Proves regularity for graphs with bounded anisotropic mean curvature and atomic energy condition.
result Regularity at boundary points with density bounded above by 1/2 + σ.
A regularized optimization problem over a large unstructured graph is studied, where the regularization term is tied to the graph geometry. Typical regularization examples include the total variation and the Laplacian regularizations over the graph. When applying the proximal gradient algorithm to solve this problem, t…
Curvature regularization prevents distortion in graph embeddings.
problem Graph topology patterns distort in Euclidean space, making detection difficult.
method Proposes curvature regularization to enforce flatness in embedding manifolds.
result Significant improvements in five embedding methods on open graph datasets.
Proposes a method for multi-view clustering that integrates consistent and complementary graph regularizers.
problem Multi-view clustering where views have both consistent and complementary information.
method Consistent and complementary graph-regularized multi-view subspace clustering (GRMSC).
result The proposed method outperforms state-of-the-art methods on benchmark datasets.
This paper presents a bias-variance tradeoff of graph Laplacian regularizer, which is widely used in graph signal processing and semi-supervised learning tasks. The scaling law of the optimal regularization parameter is specified in terms of the spectral graph properties and a novel signal-to-noise ratio parameter, whi…
Developed a framework for designing filters in spectral GCNNs with improved performance.
problem Designing effective filters for spectral GCNNs with regularization properties.
method Exploring regularization properties of graph Laplacian and proposing a generalized framework for filter design.
result New filters derived from the framework outperform state-of-the-art techniques in semi-supervised node classification.
We study a modified notion of Ollivier's coarse Ricci curvature on graphs introduced by Lin, Lu, and Yau in [11]. We establish a rigidity theorem for complete graphs that shows a connected finite simple graph is complete if and only if the Ricci curvature is strictly greater than one. We then derive explicit Ricci curv…
Proposes a new graph kernel framework using regularized Wasserstein distances.
problem Learning optimal transport distances for graph kernels.
method Introduces Regularized Wasserstein (RW) discrepancy with two regularization terms.
result Empirically validated method outperforms state-of-the-art methods.
GCN and GPCA are mathematically connected, leading to improved node classification performance.
problem Improving node classification performance in semi-supervised settings.
method Established a mathematical connection between GCN and GPCA, demonstrating their equivalence and using this to design an effective initialization strategy.
result GPCA paired with a simple MLP achieves similar or better performance than GCN on semi-supervised node classification tasks.
This paper explores the recently proposed Graph Convolutional Network architecture proposed in (Kipf & Welling, 2016) The key points of their work is summarized and their results are reproduced. Graph regularization and alternative graph convolution approaches are explored. I find that explicit graph regularization was…
Smoothness of graphs evolving by fractional mean curvature is proven.
problem Evolution of graphs by fractional mean curvature.
method Analytic semigroup approach to nonlocal quasilinear evolution equation.
result Short time existence, uniqueness, and optimal Hölder regularity of classical solutions.
The paper proves Lipschitz regularity of graph Laplacian eigenvectors on random data clouds.
problem Analyzing the regularity of solutions to graph Laplacian equations on random data points.
method Probabilistic coupling of random walks and interpolation method for point clouds to continuum.
result Graph Laplacian eigenvectors are essentially Lipschitz with constants depending on eigenvalues.
Improves graph recovery in Gaussian graphical modeling.
problem Calibrating regularization parameters for graph recovery.
method Thresholded adaptive validation applied to graphical lasso.
result Thresholding pipeline improves graph recovery.
In this article, we improve extreme learning machines for regression tasks using a graph signal processing based regularization. We assume that the target signal for prediction or regression is a graph signal. With this assumption, we use the regularization to enforce that the output of an extreme learning machine is s…
Graph embedding is an effective method to represent graph data in a low dimensional space for graph analytics. Most existing embedding algorithms typically focus on preserving the topological structure or minimizing the reconstruction errors of graph data, but they have mostly ignored the data distribution of the laten…
Proves curvature of conference graphs and finds local matchings.
problem Proving precise values of curvature in conference graphs.
method Combining parameter relations and combinatorial approach.
result Existence of local perfect matchings in broader classes of graphs.
Flexible per-class regularization improves binary classifiers.
problem Improving binary classifiers by addressing outliers and class imbalance.
method Graph-based adaptive regularization with flexible per-class thresholds.
result Flexible thresholds improve classifier performance and address class imbalance.
Fiedler regularization uses spectral graph theory to improve neural network performance.
problem Improving neural network performance by penalizing weights based on connectivity.
method Uses the Fiedler value of the neural network's graph as a regularization tool, providing theoretical and computational methods.
result Demonstrates Fiedler regularization's effectiveness in improving neural network performance.
Learning the "blocking" structure is a central challenge for high dimensional data (e.g., gene expression data). Recently, a sparse singular value decomposition (SVD) has been used as a biclustering tool to achieve this goal. However, this model ignores the structural information between variables (e.g., gene interacti…
A new method improves graph-based learning for high-dimensional data.
problem Inconsistent high-dimensional learning efficiency of semi-supervised graph regularization.
method Introducing a novel regularization approach involving centering operation.
result Empirical results show improved performance over spectral clustering.
Two regularization techniques improve GCNN explainability and preference from chemists.
problem Difficulty in rationalizing molecular graph neural network predictions.
method Batch Representation Orthonormalization (BRO) and Gini regularization applied during GCNN training.
result Regularization improves GCNN attribution methods and preference from chemists.
Unified taxonomy for graph representation learning.
problem Lack of unified understanding and integration of graph representation learning methods.
method Proposes a Graph Encoder Decoder Model (GRAPHEDM) to unify graph neural networks, network embedding, and graph regularization.
result Unified taxonomy and Graph Encoder Decoder Model (GRAPHEDM) for graph representation learning.
A new method for linear regression using feature graphs and hierarchical shrinkage.
problem Estimating robust parameters for linear regression models.
method Hierarchical Feature Regression (HFR) estimator that constructs a supervised feature graph to shrink parameters towards group targets.
result Demonstrates good predictive accuracy and versatility compared to other regularization techniques.
Quantum computing techniques improve graph analysis and community detection.
problem Analyzing large graphs efficiently and accurately.
method Used quantum annealing and quantum gate computers for community detection and regularity checking.
result Demonstrated the effectiveness of quantum computing in solving complex graph problems.
Examples of area-minimizing graphs with low regularity in a specific group.
problem Finding area-minimizing graphs with low regularity in a sub-Finsler Heisenberg group.
method Providing examples of entire area-minimizing horizontal graphs with prescribed singular sets.
result Examples of area-minimizing graphs that are locally Lipschitz but not necessarily smoother.
In this article we describe a canonical way to expand a certain kind of (Z2)n+1-colored regular graphs into closed n-manifolds by adding cells determined by the edge-colorings inductively. We show that every closed combinatorial n-manifold can be obtained in this way. When n≤3, we give simple eq…
Poisson learning doesn't solve graph semi-supervised learning issues.
problem Global information loss in graph-based semi-supervised learning.
method Poisson learning is Laplace regularization with thresholding.
result Poisson learning cannot overcome the global information loss problem.
Local graph clustering methods aim to find small clusters in very large graphs. These methods take as input a graph and a seed node, and they return as output a good cluster in a running time that depends on the size of the output cluster but that is independent of the size of the input graph. In this paper, we adopt a…
Graph embedding aims to transfer a graph into vectors to facilitate subsequent graph analytics tasks like link prediction and graph clustering. Most approaches on graph embedding focus on preserving the graph structure or minimizing the reconstruction errors for graph data. They have mostly overlooked the embedding dis…
The paper introduces a test to distinguish spatial graphs based on their knot diagrams.
problem Distinguishing isotopic spatial graphs from diagrams.
method Using the writhe of knot diagrams from cycles in the graph.
result A necessary condition for distinguishing isotopic spatial graphs.
We consider the two problems of predicting links in a dynamic graph sequence and predicting functions defined at each node of the graph. In many applications, the solution of one problem is useful for solving the other. Indeed, if these functions reflect node features, then they are related through the graph structure.…
Graph regularized autoencoder improves anomaly detection performance.
problem Unsupervised anomaly detection in high-dimensional data.
method Developed a graph regularized autoencoder using MST-based distances.
result Outperforms alternative methods on 20 benchmark anomaly detection datasets.
The paper proves optimal smoothness for certain Lagrangian graphs with specific Hölder continuity.
problem Optimal regularity for Hölder continuous Hamiltonian stationary Lagrangian graphs.
method Establishing smoothness conditions based on Hölder exponent and Lagrangian phase properties.
result Smoothness of graphs is achieved when Hölder exponent is strictly greater than 1/3 and Lagrangian phase is supercritical.
Solutions to a quadratic matrix equation are linked to strongly regular graphs and multiplicative characters.
problem Solving a specific quadratic matrix equation in Riemannian geometry.
method Constructing nonzero solutions using group rings and multiplicative characters of finite fields.
result Solutions relate to strongly regular graphs and multiplicative characters of finite fields.
Proposes a method to infer complex network topologies from multiple graphs.
problem Learning multiple graph Laplacian matrices from heterogeneous graph signals with intricate topological patterns.
method Structured fusion regularization and ADMM algorithm for efficient computation.
result Establishes a non-asymptotic bound of the estimation error and reflects the effect of key factors on convergence rate.
Immersions of graphs to the projective plane are studied. A classification of immersions up to regular homotopy is given. A complete invariant of immersions up to regular homotopy is constructed. Equivalence classes are described.
This paper introduces a method to improve GNN stability and robustness.
problem Challenges in GNN stability, generalization, and robustness.
method SVD regularization to induce contractive behavior in GNNs.
result SVD regularization enhances the stability and generalization of GNNs.
SCR improves GNN training with consistency regularization.
problem Balancing labeled and unlabeled data in GNNs.
method Introduces two consistency regularization strategies: perturbed predictions and Mean Teacher.
result Enhances various GNNs to achieve better performance.
Electronic Health Records (EHR) are high-dimensional data with implicit connections among thousands of medical concepts. These connections, for instance, the co-occurrence of diseases and lab-disease correlations can be informative when only a subset of these variables is documented by the clinician. A feasible approac…
Researchers use estimated Kolmogorov complexity for better link prediction in graphs.
problem Improving link prediction accuracy in complex networks.
method Regularization based on an approximation of Kolmogorov complexity, which is differentiable and compatible with recent link prediction algorithms.
result The regularization method shows good performance on diverse real-world networks, but the success is likely due to an aggregation method rather than actual estimation of Kolmogorov complexity.