Computationally-efficient Graph Modeling with Refined Graph Random Features
We propose refined GRFs (GRFs++), a new class of Graph Random Features (GRFs) for efficient and accurate computations involving kernels defined on the nodes of a graph. GRFs++ resolve some of the long-standing limitations of regular GRFs, including difficulty modeling relationships between more distant nodes. They reduce dependence on sampling long graph random walks via a novel walk-stitching technique, concatenating several shorter walks without breaking unbiasedness. By applying these techniques, GRFs++ inherit the approximation quality provided by longer walks but with greater efficiency, trading sequential, inefficient sampling of a long walk for parallel computation of short walks and matrix-matrix multiplication. Furthermore, GRFs++ extend the simplistic GRFs walk termination mechanism (Bernoulli schemes with fixed halting probabilities) to a broader class of strategies, applying general distributions on the walks' lengths. This improves the approximation accuracy of graph kernels, without incurring extra computational cost. We provide empirical evaluations to showcase all our claims and complement our results with theoretical analysis.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Model
Local convergence has emerged as a fundamental tool for analyzing sparse random graph models. We introduce a new notion of local convergence, color convergence, based on the Weisfeiler-Leman algorithm. Color convergence …
Video-based Sequential Bayesian Homography Estimation for Soccer Field Registration
A novel Bayesian framework is proposed, which explicitly relates the homography of one video frame to the next through an affine transformation while explicitly modelling keypoint uncertainty. The literature has previous…
Homography EstimationKeypoint DetectionStructure Learning in Graphical Modeling
A graphical model is a statistical model that is associated to a graph whose nodes correspond to variables of interest. The edges of the graph reflect allowed conditional dependencies among the variables. Graphical model…
GDPNet: Refining Latent Multi-View Graph for Relation Extraction
Relation Extraction (RE) is to predict the relation type of two entities that are mentioned in a piece of text, e.g., a sentence or a dialogue. When the given text is long, it is challenging to identify indicative words …
Dialog Relation ExtractionDynamic Time WarpingRelationRelation Extraction+2Transformation of Node to Knowledge Graph Embeddings for Faster Link Prediction in Social Networks
Recent advances in neural networks have solved common graph problems such as link prediction, node classification, node clustering, node recommendation by developing embeddings of entities and relations into vector space…
Knowledge Graph EmbeddingsLink PredictionNode ClassificationNode Clustering