Generalizes k-means to graphs using PageRank.
problem Clustering nodes in directed and undirected graphs.
method Utilizes PageRank to compute node centrality in graphs.
result Robustly computes centrality in graphs and metric spaces.
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “Generalized PageRank”
The importance of nodes in a network constantly fluctuates based on changes in the network structure as well as changes in external interest. We propose an evolving teleportation adaptation of the PageRank method to capture how changes in external interest influence the importance of a node. This framework seamlessly g…
In this paper, we discuss the sensitivity of quantum PageRank. By using the finite dimensional perturbation theory, we estimate the change of the quantum PageRank under a small analytical perturbation on the Google matrix. In addition, we will show the way to estimate the lower bound of the convergence radius as well a…
The paper finds Koopman invariant subspaces using personalized PageRank.
problem Selecting a finite dictionary of observables for Koopman-invariant span.
method Exploiting zero-block structure in EDMD matrices and applying PageRank.
result Personalized PageRank can detect Koopman invariant subspaces.
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…
During the last two decades, we easilly see that the World Wide Web's link structure is modeled as the directed graph. In this paper, we will model the World Wide Web's link structure as the directed hypergraph. Moreover, we will develop the PageRank algorithm for this directed hypergraph. Due to the lack of the World …
This paper shows that pairwise PageRank orders emerge from two-hop walks. The main tool used here refers to a specially designed sign-mirror function and a parameter curve, whose low-order derivative information implies pairwise PageRank orders with high probability. We study the pairwise correct rate by placing the Go…
Introduces NCDawareRank, a new ranking framework for networks.
problem The overlooked teleportation component in Random Surfer model.
method Exploits network meta-information and higher-order structural organization.
result NCDawareRank preserves PageRank's mathematical structure and computational characteristics.
PageRank for Semi-Supervised Learning has shown to leverage data structures and limited tagged examples to yield meaningful classification. Despite successes, classification performance can still be improved, particularly in cases of fuzzy graphs or unbalanced labeled data. To address such limitations, a novel approach…
CorePPR combines PageRank and CoreRank for scalable GNNs.
problem Expensive message passing in GNNs for large graphs.
method Learnable convex combination of approximate PPR and CoreRank, dynamic node selection.
result CorePPR outperforms PPRGo on large graphs.
The PageRank of a graph is a scalar function defined on the node set of the graph which encodes nodes centrality information of the graph. In this article, we use the PageRank function along with persistent homology to obtain a scalable graph descriptor and utilize it to compare the similarities between graphs. For a g…
New algorithm assesses credit risk in multilayer networks over time.
problem Quantifying evolving credit risk in complex, interconnected networks.
method Personalized PageRank algorithm for multilayer networks.
result Credit risk evolves and propagates through multilayer networks over time.
Community detection is, at its core, an attempt to attach an interpretable function to an otherwise indecipherable form. The importance of labeling communities has obvious implications for identifying clusters in social networks, but it has a number of equally relevant applications in product recommendations, biologica…
We introduce a new convex optimization problem, termed quadratic decomposable submodular function minimization (QDSFM), which allows to model a number of learning tasks on graphs and hypergraphs. The problem exhibits close ties to decomposable submodular function minimization (DSFM), yet is much more challenging to sol…
Neural message passing algorithms for semi-supervised classification on graphs have recently achieved great success. However, for classifying a node these methods only consider nodes that are a few propagation steps away and the size of this utilized neighborhood is hard to extend. In this paper, we use the relationshi…
InstantEmbedding efficiently generates node representations with less computation and memory.
problem Efficiently generating local node representations for large graphs.
method Local PageRank computations in sublinear time.
result Significantly faster and less memory-intensive than traditional methods.
Differentially private graph learning via bounded sensitivity PPR.
problem Protecting user data in graph learning algorithms.
method Proposes a sensitivity-bounded personalized PageRank (PPR) algorithm.
result Achieves similar accuracy to non-private algorithms with large degrees.
Study uses Google matrix analysis to show how COVID-19 changed international trade flows.
problem Impact of COVID-19 on international trade patterns.
method Google matrix analysis of World Trade Network (WTN), including PageRank, CheiRank, and reduced Google matrix.
result Significant changes in international trade flows due to the pandemic, affecting export and import balances.
Adaptive GPR-GNN optimizes node feature and topology learning.
problem Optimizing GNNs for both node features and graph topology, regardless of homophily or heterophily.
method Adaptive Universal Generalized PageRank (GPR) Graph Neural Network (GPR-GNN) that learns optimal GPR weights.
result Significant performance improvement on node classification tasks compared to state-of-the-art GNNs.
Contagion in Bitcoin networksq-fin.TR
We construct the Google matrices of bitcoin transactions for all year quarters during the period of January 11, 2009 till April 10, 2013. During the last quarters the network size contains about 6 million users (nodes) with about 150 million transactions. From PageRank and CheiRank probabilities, analogous to trade imp…
Recommendation systems are widely used by different user service providers specially those who have interactions with the large community of users. This paper introduces a recommender system based on community detection. The recommendation is provided using the local and global similarities between users. The local inf…
For researching the association between coal enterprise management and return in financial market, this paper applies the method of time difference relevance and PageRank method to seek the leader-index of a stock set containing 21 coal enterprises in A-share market and score those stocks. Based on the return in 2011, …
Reinforcement learning has gained wide popularity as a technique for simulation-driven approximate dynamic programming. A less known aspect is that the very reasons that make it effective in dynamic programming can also be leveraged for using it for distributed schemes for certain matrix computations involving non-nega…
PPRGo uses approximate PageRank to speed up GNNs on large graphs.
problem Efficiently learning on large graphs using GNNs.
method Approximates PageRank for efficient information diffusion in GNNs.
result PPRGo outperforms other methods in speed and scalability.
Jiří Matoušek (1963-2015) had many breakthrough contributions in mathematics and algorithm design. His milestone results are not only profound but also elegant. By going beyond the original objects --- such as Euclidean spaces or linear programs --- Jirka found the essence of the challenging mathematical/algorithmic pr…
Unsupervised scheme ranks sentences in text documents based on semantic importance.
problem Ranking sentences in text documents without labeled data.
method Extracts essential words and phrases, constructs semantic phrase and sentence graphs, applies PageRank, combines scores, and optimizes for topic diversity.
result SSR outperforms individual judges and compares favorably with combined rankings on benchmarks.
Repelling Random Walksstat.ML
Repelling random walks improve graph-based sampling efficiency.
problem Efficient graph-based sampling and statistical estimation.
method Induces correlations between trajectories of an ensemble of walkers on a graph, maintaining unbiasedness.
result Improves concentration of statistical estimators on graphs.
New algorithm improves fraud detection by analyzing financial account relationships.
problem High false positive rates and missed detections in conventional fraud detection systems.
method Personalized PageRank (PPR) algorithm to capture social dynamics of fraud.
result Integrating PPR enhances fraud detection model's predictive power.
Transitions between quasi-stationary states in traffic systems: Cologne orbital motorways as an examplephysics.soc-ph
Study identifies transitions between traffic modes on Cologne motorways.
problem Understanding transitions between different traffic modes.
method Constructed state transition network, identified dominant states using PageRank algorithm.
result Identified seasonal dependence in traffic modes.
New method attacks GNNs with limited node access, increasing misclassification rate.
problem Attacking GNNs with limited node access and limited attack nodes.
method Generalized gradient-based attacks using importance scores derived from random walks.
result Proposed greedy procedure significantly increases misclassification rate.
The paper provides statistical theory and intuition for personalized PageRank (called "PPR"): a popular technique that samples a small community from a massive network. We study a setting where the entire network is expensive to obtain thoroughly or to maintain, but we can start from a seed node of interest and "crawl"…
This work identifies and mitigates topological bias in HGNNs using meta-weighting and debiasing.
problem Topological bias in HGNNs affects model performance on specific nodes.
method Meta-weighting adjacency matrix, PageRank projection, debiasing structure.
result The debiasing structure improves HGNNs' performance and debiasing.
Despite the exploding interest in graph neural networks there has been little effort to verify and improve their robustness. This is even more alarming given recent findings showing that they are extremely vulnerable to adversarial attacks on both the graph structure and the node attributes. We propose the first method…
A federated method for feature selection in multi-label data.
problem Feature selection in multi-label data for distributed and federated environments.
method Semi-Supervised Federated Multi-Label Feature Selection (SSFMLFS) using fuzzy information measures.
result SSFMLFS outperforms other methods in feature selection for multi-label data in federated settings.
The paper analyzes oversmoothing in GNNs and quantifies the effects of mixing and denoising.
problem Oversmoothing in Graph Neural Networks (GNNs).
method Non-asymptotic analysis of graph convolutions and effects of mixing and denoising.
result The number of layers required for oversmoothing to occur is for dense graphs.
Deep Graphscs.LG
We propose an algorithm for deep learning on networks and graphs. It relies on the notion that many graph algorithms, such as PageRank, Weisfeiler-Lehman, or Message Passing can be expressed as iterative vertex updates. Unlike previous methods which rely on the ingenuity of the designer, Deep Graphs are adaptive to the…
Some of the most effective influential spreader detection algorithms are unstable to small perturbations of the network structure. Inspired by bagging in Machine Learning, we propose the first Perturb and Combine (P&C) procedure for networks. It (1) creates many perturbed versions of a given graph, (2) applies a node s…
We analyze the influence and interactions of 60 largest world banks for 195 world countries using the reduced Google matrix algorithm for the English Wikipedia network with 5 416 537 articles. While the top asset rank positions are taken by the banks of China, with China Industrial and Commercial Bank of China at the f…
An important problem that arises in reinforcement learning and Monte Carlo methods is estimating quantities defined by the stationary distribution of a Markov chain. In many real-world applications, access to the underlying transition operator is limited to a fixed set of data that has already been collected, without a…
Laplacian mixture models identify overlapping regions of influence in unlabeled graph and network data in a scalable and computationally efficient way, yielding useful low-dimensional representations. By combining Laplacian eigenspace and finite mixture modeling methods, they provide probabilistic or fuzzy dimensionali…
We introduce a new convex optimization problem, termed quadratic decomposable submodular function minimization. The problem is closely related to decomposable submodular function minimization and arises in many learning on graphs and hypergraphs settings, such as graph-based semi-supervised learning and PageRank. We ap…
This work estimates edge weights of edge-reinforced random walks using observed data.
problem Statistical estimation of edge weights in edge-reinforced random walks.
method Proposes an estimator based on the generalized method of moments using the magic formula and hyperbolic Gaussian structure.
result Analyzes the sample complexity of the proposed estimator.
Graph convolution is the core of most Graph Neural Networks (GNNs) and usually approximated by message passing between direct (one-hop) neighbors. In this work, we remove the restriction of using only the direct neighbors by introducing a powerful, yet spatially localized graph convolution: Graph diffusion convolution …
Composite development indicators used in policy making often subjectively aggregate a restricted set of indicators. We show, using dimensionality reduction techniques, including Principal Component Analysis (PCA) and for the first time information filtering and hierarchical clustering, that these composite indicators m…
In accessibility tests for digital preservation, over time we experience drifts of localized and labelled content in statistical models of evolving semantics represented as a vector field. This articulates the need to detect, measure, interpret and model outcomes of knowledge dynamics. To this end we employ a high-perf…
Lead-lag relationships among assets represent a useful tool for analyzing high frequency financial data. However, research on these relationships predominantly focuses on correlation analyses for the dynamics of stock prices, spots and futures on market indexes, whereas foreign exchange data have been less explored. To…
Recommending appropriate items to users is crucial in many e-commerce platforms that contain implicit data as users' browsing, purchasing and streaming history. One common approach consists in selecting the N most relevant items to each user, for a given N, which is called top-N recommendation. To do so, recommender sy…
Recent advancements in graph representation learning have led to the emergence of condensed encodings that capture the main properties of a graph. However, even though these abstract representations are powerful for downstream tasks, they are not equally suitable for visualisation purposes. In this work, we merge Mappe…