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.
Paper defends sensitive attributes in GNNs from inference attacks.
problem Protecting sensitive attributes in GNNs from inference attacks.
method Proposes adversarial training with TV and Wasserstein distance to locally filter sensitive attributes.
result Framework creates strong defense against inference attacks with minimal performance loss.
FairGP uses graph partitioning to make Graph Transformers fair and scalable.
problem Fairness issues in Graph Transformers, especially against sensitive features.
method Graph partitioning to minimize the influence of higher-order nodes and optimize attention mechanisms.
result FairGP improves fairness in Graph Transformers while reducing computational complexity.
Paper analyzes GCNN sensitivity to probabilistic graph perturbations.
problem Investigating how GCNNs handle probabilistic graph errors.
method Establishes error bounds and linear relationships between GSO perturbations and GCNN outputs.
result GCNNs maintain stability under graph edge perturbations if GSO errors are bounded.
Enhances GNNs by capturing node relationships, outperforming 2-WL test.
problem Inability of conventional GNNs to fully capture node relationships due to permutation invariance.
method Develops permutation-sensitive aggregation mechanism using permutation groups.
result Proves superior expressivity compared to 2-WL test and not less than 3-WL test.
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…
GOAT learns multiple node representations from graph structure alone.
problem Context-free graph representation learning limits model performance.
method Inspired by gossip and mutual attention, GOAT learns multiple node representations.
result GOAT outperforms 12 SOTA baselines on link prediction and clustering tasks.
Privacy-preserving GNNs for graph data with sensitive node data.
problem Privacy concerns in learning node representations for graphs with sensitive data.
method Developed a privacy-preserving GNN learning algorithm based on Local Differential Privacy (LDP). Proposed an LDP encoder, an unbiased rectifier, and a denoising mechanism (KProp).
result Our method maintains a satisfying level of accuracy with low privacy loss.
Paper improves robustness of GNNs against adversarial attacks.
problem Understanding robust generalization of GNNs in adversarial settings.
method Develops a sensitivity-aware PAC-Bayesian framework for MPGNNs.
result Derives tighter robust generalization bounds for MPGNNs.
Consistent spectral clustering with fairness constraints on representation graphs.
problem Finding balanced clusters in similarity graphs with fairness constraints.
method Developed variants of unnormalized and normalized spectral clustering for fair planted partitions.
result Consistency results for constrained spectral clustering under fair planted partitions.
New method mitigates bias without sensitive data using causal graph and variational autoencoder.
problem Lack of fairness strategies when sensitive attributes are not collected.
method SRCVAE framework based on causal graph for inferring a proxy sensitive attribute.
result Significant improvements in fairness metrics over existing methods.
Proposes a method to learn graph structure and model parameters jointly in LRSM.
problem The sensitivity of graph weights in LRSM can be arbitrarily large under imbalanced scales and sample sizes.
method Jointly learns graph structure and model parameters by solving a single optimization problem, providing convergence guarantees.
result The proposed approach outperforms existing methods in various real-world numerical examples.
This paper debiases KG embeddings by filtering sensitive attributes.
problem Social and cultural biases in KG representations.
method Exploring and filtering popularity and gender biases in KGE.
result Sensitivity of KG embeddings to sensitive attributes like gender.
Framework achieves fairness in predictions using partially known causal graph over clusters of variables.
problem Achieving fairness in algorithmic decisions when causal graph knowledge is limited.
method Leverages a causal graph over clusters of variables to train a prediction model, reducing interventional distribution discrepancies.
result Framework strikes a better balance between fairness and accuracy than existing approaches under limited causal graph knowledge.
New method for fair influence maximization in social networks.
problem Maximizing influence while ensuring fairness across sensitive attributes.
method Co-training an auto-encoder and discriminator to create fair graph embeddings.
result Our method reduces disparity while maintaining competitive influence maximization performance.
Sketch-GNN reduces GNN training time and memory usage to sublinear scales.
problem Training GNNs on large graphs is computationally expensive and memory-intensive.
method Develops a sketch-based algorithm that trains GNNs on compact sketches of graph adjacency and node embeddings.
result Training time and memory usage grow sublinearly with respect to graph size.
Method reduces model bias in water temperature prediction using physics-guided GNNs.
problem Model bias in traditional physics-based models across different income and education levels.
method Physics-guided GNNs with refined neighbor selection and weights.
result Preserves equitable performance across different sensitive groups in the Delaware River Basin.
While biomanufacturing plays a significant role in supporting the economy and ensuring public health, it faces critical challenges, including complexity, high variability, lengthy lead time, and very limited process data, especially for personalized new cell and gene biotherapeutics. Driven by these challenges, we prop…
Generates low-dimensional node vectors for graphs with privacy while preserving structural preferences.
problem Publishing graph node vectors can leak sensitive individual information.
method SE-PrivGEmb, a skip-gram based technique with a unified noise tolerance mechanism and negative sampling probabilities.
result Our method outperforms existing methods in structural equivalence and link prediction tasks.
Graph embedding provides an efficient solution for graph analysis by converting the graph into a low-dimensional space which preserves the structure information. In contrast to the graph structure data, the i.i.d. node embedding can be processed efficiently in terms of both time and space. Current semi-supervised graph…
PARD generates graphs efficiently and invariantly to node ordering.
problem Graph generation sensitivity to node ordering.
method Integrates autoregressive and diffusion models with a partial order for nodes and edges.
result PARD achieves state-of-the-art performance on molecular and non-molecular datasets.
We present a graph-theoretical approach to data clustering, which combines the creation of a graph from the data with Markov Stability, a multiscale community detection framework. We show how the multiscale capabilities of the method allow the estimation of the number of clusters, as well as alleviating the sensitivity…
Many computational models were proposed to extract temporal patterns from clinical time series for each patient and among patient group for predictive healthcare. However, the common relations among patients (e.g., share the same doctor) were rarely considered. In this paper, we represent patients and clinicians relati…
QSAR models struggle to predict activity cliffs, but graph isomorphism features improve AC-sensitivity.
problem QSAR models struggle to predict activity cliffs (ACs).
method Nine distinct QSAR models combining molecular representation methods and regression techniques.
result Graph isomorphism features improve AC-sensitivity.
MAPPING debiases GNNs for fair node classification with limited leakage.
problem Graph Neural Networks inherit and exacerbate historical discrimination in high-stake domains.
method MAPPING uses distance covariance-based fairness constraints and adversarial debiasing.
result MAPPING achieves better trade-offs between fairness and utility, mitigating privacy risks.
Reinforcement learning (RL) tasks are challenging to implement, execute and test due to algorithmic instability, hyper-parameter sensitivity, and heterogeneous distributed communication patterns. We argue for the separation of logical component composition, backend graph definition, and distributed execution. To this e…
Grale designs graphs for graph learning, improving performance on large datasets.
problem Finding the right graph for semi-supervised learning with billions of nodes.
method Fuses multiple similarity measures using locality sensitive hashing to create task-specific graphs.
result Grale detects a large number of malicious actors, increasing recall by 89%.
Enhances LightGCN for credit bond recommendations with dynamic node embeddings.
problem Challenges in static embeddings for rapidly evolving user interests in finance.
method Causal graph convolution for dynamic node embeddings over chronological user-item interactions.
result Significantly enhances LightGCN performance in financial product recommendations.
Transformer model pretrains on synthetic graphs for AD detection.
problem Limited labeled data and class imbalance in AD diagnosis.
method Diffusion-generated synthetic graphs, Graph Transformers, transfer learning.
result Framework outperforms baselines in AD diagnosis metrics.
Novel Haar-Laplacian for directed graphs enhances spectral graph applications.
problem Lack of suitable Laplacian for directed graphs in spectral graph theory.
method Inspired by Haar-like transformation, introduces a Hermitian matrix preserving direction and weight.
result HaarNet outperforms in weight prediction and denoising on directed graphs.
Representing entities and relations in an embedding space is a well-studied approach for machine learning on relational data. Existing approaches, however, primarily focus on improving accuracy and overlook other aspects such as robustness and interpretability. In this paper, we propose adversarial modifications for li…
This paper explores different graph neural network functions to improve graph isomorphism.
problem Lack of robust implementation for graph neural networks due to limited analysis of underlying functions.
method Examines various alternative functions for different modules in GNNs using benchmark datasets.
result Generally used underlying techniques do not always capture the overall graph structure.
The accuracy of probability distributions inferred using machine-learning algorithms heavily depends on data availability and quality. In practical applications it is therefore fundamental to investigate the robustness of a statistical model to misspecification of some of its underlying probabilities. In the context of…
New Riemannian GNNs reduce over-squashing in graphs with negative curvature.
problem Over-squashing in Riemannian graph neural networks.
method Generalization of Hyperbolic GNNs to Riemannian manifolds of variable curvature.
result Bounds on sensitivity of node features in Riemannian GNNs as layers increase.
Graph classification receives a great deal of attention from the non-Euclidean machine learning community. Recent advances in graph coarsening have enabled the training of deeper networks and produced new state-of-the-art results in many benchmark tasks. We examine how these architectures train and find that performanc…
We propose a non-parametric link prediction algorithm for a sequence of graph snapshots over time. The model predicts links based on the features of its endpoints, as well as those of the local neighborhood around the endpoints. This allows for different types of neighborhoods in a graph, each with its own dynamics (e.…
Constructing the adjacency graph is fundamental to graph-based clustering. Graph learning in kernel space has shown impressive performance on a number of benchmark data sets. However, its performance is largely determined by the chosen kernel matrix. To address this issue, the previous multiple kernel learning algorith…
This study applies EMD to MSCI World index and converts IMFs into graphs for GNN modeling.
problem Modeling financial time series with GNNs.
method EMD, CEEMDAN, graph transformations (natural visibility, horizontal visibility, recurrence, transition graphs), topological analysis.
result High-frequency IMFs yield dense, highly connected small-world graphs; low-frequency IMFs produce sparser networks.
Regularization improves spectral embedding by focusing on the largest blocks.
problem Improving the quality of spectral embedding for graph data.
method Explained the impact of complete graph regularization on spectral embedding of a block model.
result Regularization forces spectral embedding to focus on the largest blocks, making it less sensitive to noise or outliers.
Two log-linear approximations speed up optimal transport for deep learning applications.
problem Computing optimal transport in high dimensions is computationally expensive.
method Locality-sensitive hashing (LSH) and Nyström approximation with LSH-based sparse corrections.
result Log-linear time algorithms for entropy-regularized OT perform well in high-dimensional spaces.
New method for learning on heterogeneous graphs without meta-paths.
problem Learning on heterogeneous graphs is sensitive to meta-paths choice, leading to poor performance.
method Decompose heterogeneous graph into homogeneous relation-type graphs, combine higher-order representations, use attention mechanisms.
result Our model outperforms state-of-the-art baselines in vertex classification tasks on heterogeneous graph datasets.
APGE protects graph node representations from inference attacks.
problem Privacy leakage in graph embedding methods.
method Adversarial training framework with disentangling and purging mechanisms.
result APGE preserves structural and utility attributes while concealing private information.
Spectral clustering (SC) and graph-based semi-supervised learning (SSL) algorithms are sensitive to how graphs are constructed from data. In particular if the data has proximal and unbalanced clusters these algorithms can lead to poor performance on well-known graphs such as k-NN, full-RBF, ε-graphs. This is becaus…
GAP learns node representations by attending to different parts of its neighborhood.
problem Context-free learning of node representations in graph representation learning.
method Graph Neighborhood Attentive Pooling (GAP) using attentive pooling networks.
result GAP outperforms 10 state-of-the-art methods on link prediction and clustering tasks.
We introduce colorings of oriented surface-links by biquasiles using marked graph diagrams. We use these colorings to define counting invariants and Boltzmann enhancements of the biquasile counting invariants for oriented surface-links. We provide examples to show that the invariants can distinguish both closed surface…
This paper detects function-level obfuscation in binary code using graph-based methods.
problem Detecting and characterizing function-level obfuscation in binary code.
method Graph-based approaches, including GNNs, are compared on various datasets.
result GNNs outperform baselines in function-level obfuscation detection, especially in a 11-class classification task.
Graph embedding leaks sensitive graph properties and subgraphs.
problem Privacy risks in graph embedding sharing.
method Three inference attacks and a defense mechanism.
result High accuracy in inferring graph properties and subgraphs.
We propose a nonparametric approach to link prediction in large-scale dynamic networks. Our model uses graph-based features of pairs of nodes as well as those of their local neighborhoods to predict whether those nodes will be linked at each time step. The model allows for different types of evolution in different part…