Kiarash Zahirnia, Ankita Sakhuja, Oliver Schulte et al. · arXiv (Cornell University) · 2021
Recent work on graph generative models has made remarkable progress towards generating increasingly realistic graphs, as measured by global graph features such as degree distribution, density, and clustering coefficients. Deep generative models have also made significant advances through better modelling of the local correlations in the graph topology, which have been very useful for predicting unobserved graph components, such as the existence of a link or the class of a node, from nearby observed graph components. A complete scientific understanding of graph data should address both global and local structure. In this paper, we propose a joint model for both as complementary objectives in a graph VAE framework. Global structure is captured by incorporating graph kernels in a probabilistic model whose loss function is closely related to the maximum mean discrepancy(MMD) between the global structures of the reconstructed and the input graphs. The ELBO objective derived from the model regularizes a standard local link reconstruction term with an MMD term. Our experiments demonstrate a significant improvement in the realism of the generated graph structures, typically by 1-2 orders of magnitude of graph structure metrics, compared to leading graph VAEand GAN models. Local link reconstruction improves as well in many cases.
Cited by 0Open access
Justin A. Eichel (502037), Alexander Wong (283533), Paul Fieguth (502038) et al. · Figshare · 2015
<p>The effects of increasing the size of the graph kernel, , and increasing the size of the sub-graph kernel, , are illustrated using a two-dimensional example above. As the size of increases, from top to bottom, the size of the neighbourhood (solid dark blue) surrounding (dark red) increases. As the size of increases, from left to right, the size of the sub-graphs (light red and light green) increases. Increasing the size of decreases the sparsity of <i>W</i> and increasing the size of increases the computational complexity of calculating , but only moderately.</p>
Cited by 0Open access
Jiaqi Zhang, Liu, Cheng-Lin, Xiaoyi Jiang · Zenodo (CERN European Organization for Nuclear Research) · 2023
Interpolating classifiers interpolate all the training data and thus have zero training error. Recent research shows their fundamental importance for high-performance ensemble techniques. Interpolation kernel machines belong to the class of interpolating classifiers and do generalize well. They have been demonstrated to be a good alternative to support vector machine for graph classification. In this work we further improve their performance by considering multiple kernel learning. We establish a general scheme for achieving this goal. The current experimental work is done using quadratic kernel combination. Our experimental results demonstrate the performance boosting potential of our approach against the use of individual graph kernels.
Cited by 0Open access
Xiang Chen, Kun Yue, Wenjie Liu et al. · Proceedings of the AAAI Conference on Artificial Intelligence · 2026
Graph Contrastive Learning (GCL) has emerged as a powerful paradigm for training Graph Neural Networks (GNNs) in the absence of task-specific labels. However, its scalability on large-scale graphs is hindered by the intensive message passing mechanism of GNN and the quadratic computational complexity of contrastive loss over positive and negative node pairs. To address these issues, we propose an efficient GCL framework that transforms the input graph into a compact network of interconnected node sets while preserving structural information across communities. We firstly introduce a kernelized graph community contrastive loss with linear complexity, enabling effective information transfer among node sets to capture hierarchical structural information of the graph. We then incorporate a knowledge distillation technique into the decoupled GNN architecture to accelerate inference while maintaining strong generalization performance. Extensive experiments on sixteen real-world datasets of varying scales demonstrate that our method outperforms state-of-the-art GCL baselines in both effectiveness and scalability.
Cited by 0Open access
Gogineni, Vinay Chakravarthi, Naumova, Valeriya, Werner, Stefan et al. · Duo Research Archive (University of Oslo) · 2022
This paper presents graph kernel adaptive filters that model nonlinear input-output relationships of streaming graph signals. To this end, we propose centralized and distributed graph kernel recursive least-squares (GKRLS) algorithms utilizing the random Fourier features (RFF) map. Compared with solutions based on the traditional kernel trick, the proposed RFF approach presents two significant advantages. First, it sidesteps the need to maintain a high-dimensional dictionary, whose dimension increases with the number of graph nodes and time, which renders prohibitive computational and storage costs, especially when considering least-squares algorithms involving matrix inverses. Second, the distributed algorithm developed in this paper, referred to here as the graph diffusion kernel recursive least-squares (GDKRLS) algorithm, does not require centralized dictionary training, making it ideal for distributed learning in dynamic environments. To examine the performance of the proposed algorithms, we analyze the mean convergence of the GDKRLS algorithm and conduct numerical experiments. Results confirm the superiority of the proposed RFF-based GKRLS and GDKRLS over their LMS counterparts.
Cited by 15Open access
Benoît Gaüzère, Luc Brun, Didier Villemin · HAL (Le Centre pour la Communication Scientifique Directe) · 2014
International audience
Cited by 0Open access
Michael M. Bronstein, Klaus Glashoff · 2013
Cited by 0
Lixiang Xu, Jin Xie, Xiaofeng Wang et al. · Lecture notes in computer science · 2015
Cited by 3
Till Hendrik Schulz, Tamás Horváth, Pascal Welke et al. · Machine Learning · 2022
Abstract After more than one decade, Weisfeiler-Lehman graph kernels are still among the most prevalent graph kernels due to their remarkable predictive performance and time complexity. They are based on a fast iterative partitioning of vertices, originally designed for deciding graph isomorphism with one-sided error. The Weisfeiler-Lehman graph kernels retain this idea and compare such labels with respect to equality. This binary valued comparison is, however, arguably too rigid for defining suitable graph kernels for certain graph classes. To overcome this limitation, we propose a generalization of Weisfeiler-Lehman graph kernels which takes into account a more natural and finer grade of similarity between Weisfeiler-Lehman labels than equality. We show that the proposed similarity can be calculated efficiently by means of the Wasserstein distance between certain vectors representing Weisfeiler-Lehman labels. This and other facts give rise to the natural choice of partitioning the vertices with the Wasserstein k-means algorithm. We empirically demonstrate on the Weisfeiler-Lehman subtree kernel, which is one of the most prominent Weisfeiler-Lehman graph kernels, that our generalization significantly outperforms this and other state-of-the-art graph kernels in terms of predictive performance on datasets which contain structurally more complex graphs beyond the typically considered molecular graphs.
Cited by 33Open access
Rui-Yu Li, Yu Guo, Bin Zhang · Information · 2023
Nonnegative matrix factorization (NMF) is an efficient method for feature learning in the field of machine learning and data mining. To investigate the nonlinear characteristics of datasets, kernel-method-based NMF (KNMF) and its graph-regularized extensions have received much attention from various researchers due to their promising performance. However, the graph similarity matrix of the existing methods is often predefined in the original space of data and kept unchanged during the matrix-factorization procedure, which leads to non-optimal graphs. To address these problems, we propose a kernel-graph-learning-based, nonlinear, nonnegative matrix-factorization method in this paper, termed adaptive kernel graph nonnegative matrix factorization (AKGNMF). In order to automatically capture the manifold structure of the data on the nonlinear feature space, AKGNMF learned an adaptive similarity graph. We formulated a unified objective function, in which global similarity graph learning is optimized jointly with the matrix decomposition process. A local graph Laplacian is further imposed on the learned feature subspace representation. The proposed method relies on both the factorization that respects geometric structure and the mapped high-dimensional subspace feature representations. In addition, an efficient iterative solution was derived to update all variables in the resultant objective problem in turn. Experiments on the synthetic dataset visually demonstrate the ability of AKGNMF to separate the nonlinear dataset with high clustering accuracy. Experiments on real-world datasets verified the effectiveness of AKGNMF in three aspects, including clustering performance, parameter sensitivity and convergence. Comprehensive experimental findings indicate that, compared with various classic methods and the state-of-the-art methods, the proposed AKGNMF algorithm demonstrated effectiveness and superiority.
Cited by 3Open access
Benoît Gaüzère, Luc Brun, Didier Villemin · 2014
Chemo informatics aims to predict molecular properties using informational methods. Computer science's research fields concerned by this domain are machine learning and graph theory. An interesting approach consists in using graph kernels which allow to combine graph theory and machine learning frameworks. Graph kernels allow to define a similarity measure between molecular graphs corresponding to a scalar product in some Hilbert space. Most of existing graph kernels proposed in chemo informatics do not allow to explicitly encode cyclic information, hence limiting the efficiency of these approaches. In this paper, we propose to define a cyclic representation encoding the relative positioning of substituents around a cycle. We also propose a graph kernel taking into account this information. This contribution has been tested on three classification problems proposed in chemo informatics.
Cited by 3
Sakthi Kumar Arul Prakash, Tucker, Conrad S. · Code Ocean · 2021
This is the official code of the paper titled, "Node Classification using Kernel Propagation in Graph Neural Networks" which has been accepted for publication in the journal Expert Systems with Applications.
Cited by 0Open access
Till Hendrik Schulz, Tamás Horváth, Pascal Welke et al. · arXiv (Cornell University) · 2021
The Weisfeiler-Lehman graph kernels are among the most prevalent graph kernels due to their remarkable time complexity and predictive performance. Their key concept is based on an implicit comparison of neighborhood representing trees with respect to equality (i.e., isomorphism). This binary valued comparison is, however, arguably too rigid for defining suitable similarity measures over graphs. To overcome this limitation, we propose a generalization of Weisfeiler-Lehman graph kernels which takes into account the similarity between trees rather than equality. We achieve this using a specifically fitted variation of the well-known tree edit distance which can efficiently be calculated. We empirically show that our approach significantly outperforms state-of-the-art methods in terms of predictive performance on datasets containing structurally more complex graphs beyond the typically considered molecular graphs.
Cited by 1Open access
Xiang Chen, Kun Yue, Wenjie Liu et al. · ArXiv.org · 2025
Graph Contrastive Learning (GCL) has emerged as a powerful paradigm for training Graph Neural Networks (GNNs) in the absence of task-specific labels. However, its scalability on large-scale graphs is hindered by the intensive message passing mechanism of GNN and the quadratic computational complexity of contrastive loss over positive and negative node pairs. To address these issues, we propose an efficient GCL framework that transforms the input graph into a compact network of interconnected node sets while preserving structural information across communities. We firstly introduce a kernelized graph community contrastive loss with linear complexity, enabling effective information transfer among node sets to capture hierarchical structural information of the graph. We then incorporate a knowledge distillation technique into the decoupled GNN architecture to accelerate inference while maintaining strong generalization performance. Extensive experiments on sixteen real-world datasets of varying scales demonstrate that our method outperforms state-of-the-art GCL baselines in both effectiveness and scalability.
Cited by 0Open access
Furqan Aziz, Richard C. Wilson, Edwin R. Hancock · 2014
Graph based methods have been successfully used in computer vision for classification and matching. This is due to the fact that shapes can be conveniently represented using graph structures. In this paper we explore the use of a spectral invariant which is based on the wave kernel trace to characterize graphs. The wave kernel is the solution of wave equation defined using the Edge-based Laplacian of a graph. The advantage of using the edge-based Laplacian over its vertex-based counterpart is that it can be used to translate equations from continuous analysis to the discrete graph theoretic domain, that have no meanings if defined using vertex-based Laplacian. To illustrate the utility of the proposed method we apply it to graphs extracted from both three-dimensional shapes and images.
Cited by 1
Yangyang Chen (1721638), Hao Ji (6205247) · Figshare · 2024
<div><p>To provide a reference for the realization of children’s equal inheritance, this study examined the influence of child structure and means of eldercare on equitable family property distribution willingness. Using data from surveys of Chinese women’s social status, this study analyzes the impacts of child structure and means of eldercare on family property distribution, with the children’s surname choice and women’s status as moderating factors. The results indicate that a child structure in which the family consists of more girls than boys, a higher number of children, and the choice of family support for eldercare significantly inhibit the equal distribution of family assets. However, the weakening of traditional views significantly promotes the equal distribution of household assets. These findings remain robust after endogenous and robustness tests. Moreover, the study finds that the impact of the structure of children and eldercare methods varied across different age groups, household registration attributes, and genders. Research on the willingness to distribute household wealth aids in understanding the effects and differences brought about by the structure of children and eldercare methods under current traditional cultural contexts, thereby promoting a more equitable distribution of household wealth.</p></div>
Cited by 0Open access
Aymen Ourdjini, Abd Errahmane Kiouche, Hamida Seba · Lecture notes in computer science · 2023
Cited by 0
Pierre-anthony Grenier, Luc Brun, Didier Villemin · 2013
Cited by 0
卢桂馥, 林忠, 金忠 et al. · Journal of Image and Graphics · 2011
Cited by 0Open access
Thomas Gärtner · 2005
Cited by 9