Novel method HAO mitigates Graph Injection Attack by preserving homophily.
problem Graph Injection Attack's high flexibility can harm graph homophily.
method Introduce homophily unnoticeability constraint and Harmonious Adversarial Objective (HAO).
result GIA with HAO breaks homophily-based defenses and outperforms previous attacks.
A new GNN framework for graphs with heterophily.
problem Graphs with heterophily (nodes from different classes often connected).
method CPGNN framework with an interpretable compatibility matrix.
result CPGNN achieves state-of-the-art results in heterophily settings.
MPNNs struggle with class-bottlenecks and heterophily, leading to performance limitations.
problem Performance limitations of MPNNs under heterophily and structural bottlenecks.
method A statistical framework decomposing model performance into SNR components and proving bounds on sensitivity.
result Optimal graph structures for maximizing higher-order homophily are disjoint unions of single-class and two-class-bipartite clusters.
Graph neural networks struggle with heterophily, but new designs improve their performance.
problem Graph neural networks struggle with heterophily (networks where connected nodes may have different class labels and dissimilar features).
method Ego- and neighbor-embedding separation, higher-order neighborhoods, and combination of intermediate representations.
result The identified designs increase the accuracy of GNNs by up to 40% and 27% over models without them on synthetic and real networks with heterophily, respectively.
GCNs perform well on heterophilous graphs under certain conditions.
problem The necessity of homophily for good GNN performance.
method Empirical evaluation and theoretical analysis of GCNs on heterophilous graphs.
result GCNs can achieve strong performance on heterophilous graphs under certain conditions.
GCNs help in diagnosing label scarcity and feature quality on graphs.
problem Understanding when GCNs improve node classification.
method Simulated label scarcity, feature ablation, and per-class analysis.
result GCNs provide largest gains under extreme label scarcity, matching original performance with noisy features, but hurt when homophily is low and features are strong.
New spectral clustering method handles discrete covariates for better community detection.
problem Community detection in networks with discrete covariates.
method Spectral algorithm that separates latent network structure from observed covariates.
result Achieves perfect clustering with high probability in large, sparse networks.
Model distinguishes homophily and triadic closure in network analysis.
problem Conflated properties of homophily and transitivity in network analysis.
method Generative model with triadic closure edges and inference procedure.
result Can identify mechanisms responsible for network edges and community structure.
Study finds corporate boards with women appoint more women, leading to better profitability.
problem Influence of female board members on corporate profitability.
method Analysis of Japanese corporate boards and their interlocks.
result Corporate boards with women appoint more women, leading to higher profitability.
Study shows peers' graduation improves residents' success in TCs.
problem Identifying peer influence in therapeutic communities adjusting for latent homophily.
method Used data on affirmations and exit dates to form peer networks, modeled latent homophily, and proposed bias correction methods.
result Positive effect of peers' graduation on residents' graduation, varying by gender, race, and role model definition.
New framework analyzes belief evolution in social networks.
problem Analyzing belief evolution in social networks.
method Proposes a new theoretical framework using Markov chain theory for horizontal and vertical transmission.
result Homophily-based networks do not converge to a single set of beliefs.
SCNode improves node embeddings for GNNs in both homophilic and heterophilic graphs.
problem Challenges in node representation quality and generalization in GNNs, especially in heterophilic graphs.
method SCNode integrates spatial and contextual information to create more discriminative and structurally aware node embeddings.
result SCNode achieves superior performance over conventional GNN models on benchmark datasets.
GraphACL learns graph representations without augmentation or homophily assumptions.
problem Learning graph representations on heterophilic graphs (nodes with different labels and features).
method Asymmetric Contrastive Learning for Graphs (GraphACL) considers an asymmetric view of neighboring nodes.
result GraphACL significantly outperforms state-of-the-art methods on both homophilic and heterophilic graphs.
FairDrop improves fairness in graph representation learning by counteracting homophily.
problem Ensuring fairness in graph representation learning, especially in scenarios with protected attributes.
method Proposes a biased edge dropout algorithm (FairDrop) to counteract homophily and improve fairness.
result Successfully improves fairness in all models up to a small or negligible drop in accuracy.
Many widely studied graphical models with latent variables lead to nontrivial constraints on the distribution of the observed variables. Inspired by the Bell inequalities in quantum mechanics, we refer to any linear inequality whose violation rules out some latent variable model as a "hidden variable test" for that mod…
Estimates peer influence effects using embeddings for social networks.
problem Estimating peer contagion effects in social networks with unobserved confounders.
method Nonparametrically adjusts for homophily using node embeddings.
result Formalizes causal effect of peer influence in social networks.
GCNs learn by embedding similar nodes within a class and leveraging consistent neighborhood structures.
problem Understanding how GCNs perform semi-supervised node classification on both homophilous and heterophilous graphs.
method Investigated the latent node embeddings and neighborhood structures of GCNs.
result GCNs learn by embedding similar nodes within a class and leveraging consistent neighborhood structures.
Rewiring GNNs to optimize community and feature alignment improves their performance.
problem Improving GNNs' performance by addressing over-squashing and generalization issues.
method Three rewiring strategies: ComMa, FeaSt, and ComFy, targeting community structure, node labels, and their alignment.
result Rewiring strategies enhance GNNs' performance by optimizing label-community alignment.
Improved graph attention model for noisy graphs.
problem Understanding and improving graph attention in noisy graphs.
method Proposes SuperGAT, a self-supervised graph attention network.
result SuperGAT learns more expressive attention by encoding edges.
ECGs improve GNNs for non-homophilic data.
problem Improving GNNs for datasets where nodes are not likely to belong to the same class.
method ECGs rewire GNNs' computation graph to connect nodes likely in the same class using weaker classifiers.
result ECGs improve GNN performance on non-homophilic datasets.
GNNs generalize better on homophilic graphs than heterophilic ones.
problem Understanding the generalization error of GNNs on graph data.
method Analytical tools from statistical physics and random matrix theory.
result Risk is shaped by graph noise, feature noise, and training labels.
Heterophily affects GNN robustness; separating ego- and neighbor-embeddings improves defense.
problem The robustness of GNNs to adversarial attacks.
method Formalized relation between heterophily and GNN robustness; empirical analysis; design principles for improved robustness.
result Separating ego- and neighbor-embeddings increases GNN robustness.
New non-homophilous graph datasets and methods for scalable learning.
problem Evaluation of graph learning methods on non-homophilous graphs.
method Introducing LINKX, a simple yet strong method for scalable non-homophilous graph learning.
result LINKX achieves state-of-the-art performance on non-homophilous graphs.
Model shows how diversity on corporate boards influences decision-making and innovation.
problem Understanding dynamics of diversity and innovation in corporate boards.
method Developed a dynamic model calibrated with empirical data of firm and board networks.
result Homophily and visibility biases shape the trajectory towards equality in corporate boards.
New method reveals why GNNs perform well on certain datasets.
problem Understanding why GNNs perform differently on similar datasets.
method Deriving exact generalization error for various GNN architectures.
result Benchmark datasets favor architectures that rely on graph structure.
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.
ES-MLP combines Graph-MLP with edge splitting for node classification on both homophilic and heterophilic graphs.
problem Node classification on graphs with mixed homophilic and heterophilic properties.
method Combines Graph-MLP with edge splitting mechanism from ES-GNN to learn two adjacency matrices based on relevant and irrelevant feature pairs.
result ES-MLP achieves performance comparable to homophilic and heterophilic models without using edges during inference.
A hierarchical gamma process infinite edge partition model is proposed to factorize the binary adjacency matrix of an unweighted undirected relational network under a Bernoulli-Poisson link. The model describes both homophily and stochastic equivalence, and is scalable to big sparse networks by focusing its computation…
We analyze the information-theoretic limits for the recovery of node labels in several network models. This includes the Stochastic Block Model, the Exponential Random Graph Model, the Latent Space Model, the Directed Preferential Attachment Model, and the Directed Small-world Model. For the Stochastic Block Model, the…
Paper proposes JDR to denoise graph features and rewire graphs for better node classification.
problem Jointly denoise noisy graph features and rewire graphs for improved node classification.
method Align leading spectral spaces of graph and feature matrices to solve non-convex optimization problem.
result JDR consistently outperforms existing methods on various node classification tasks.
Network embedding algorithms are able to learn latent feature representations of nodes, transforming networks into lower dimensional vector representations. Typical key applications, which have effectively been addressed using network embeddings, include link prediction, multilabel classification and community detectio…
In many applications of network analysis, it is important to distinguish between observed and unobserved factors affecting network structure. To this end, we develop spectral estimators for both unobserved blocks and the effect of covariates in stochastic blockmodels. On the theoretical side, we establish asymptotic no…
Generative model controls heterophily in graph signals.
problem Controlling heterophily in graph signals for better model effectiveness.
method Combines graphon-based generator with spectral filtering of Gaussian node features.
result Establishes theoretical guarantees for heterophily control and convergence.
New kernel improves graph learning with fewer labeled data.
problem Limited kernels for node-level problems on graphs.
method Derived from a regularization framework, transductive kernel for graphs with node features.
result Improved learning on fewer training points and non-Euclidean data.
Study N-player and mean-field games in Itô-diffusion markets with competitive or homophilous interactions.
problem Optimal portfolio choice in a common market with N interacting players. method Analyzes N-player and mean-field games in incomplete and complete markets with CARA utilities and random risk tolerances. result Derives explicit or closed-form solutions for equilibrium processes and game values.
In this paper, we introduce a new online decision making paradigm that we call Thresholding Graph Bandits. The main goal is to efficiently identify a subset of arms in a multi-armed bandit problem whose means are above a specified threshold. While traditionally in such problems, the arms are assumed to be independent, …
Aggregate and systemic risk in complex systems are emergent phenomena depending on two properties: the idiosyncratic risks of the elements and the topology of the network of interactions among them. While a significant attention has been given to aggregate risk assessment and risk propagation once the above two propert…
Latent space models are effective tools for statistical modeling and exploration of network data. These models can effectively model real world network characteristics such as degree heterogeneity, transitivity, homophily, etc. Due to their close connection to generalized linear models, it is also natural to incorporat…
Method estimates heterogeneous causal effects on networks using orthogonal learning.
problem Challenges in estimating causal effects on networks due to treatment effects on both treated and neighbors, and network homophily.
method Two-stage orthogonal learning framework: first stage uses graph neural networks for nuisance components, second stage residualizes and interpretable attention-based model for causal effects.
result Improves heterogeneous effect estimation and supports interpretable analyses.
Our usage of language is not solely reliant on cognition but is arguably determined by myriad external factors leading to a global variability of linguistic patterns. This issue, which lies at the core of sociolinguistics and is backed by many small-scale studies on face-to-face communication, is addressed here by cons…
Paper tackles self-supervised learning for non-homophilous graphs.
problem Existing self-supervised learning methods assume homophilous graphs, but real-world graphs often lack this assumption.
method Develops a decoupled self-supervised learning (DSSL) framework that decouples different semantics between neighborhoods.
result DSSL framework achieves better performance on various graph benchmarks compared to competitive baselines.
Road networks are a type of spatial network, where edges may be associated with qualitative information such as road type and speed limit. Unfortunately, such information is often incomplete; for instance, OpenStreetMap only has speed limits for 13% of all Danish road segments. This is problematic for analysis tasks th…
This paper develops a coreset method for GNNs that speeds up training on large graphs.
problem Training Graph Neural Networks (GNNs) on large-scale graphs is computationally expensive.
method The paper proposes a spectral greedy coreset (SGGC) method that selects ego-graphs based on spectral embeddings.
result SGGC significantly speeds up GNN training on large graphs and outperforms other coreset methods.
Clustering is one of the most universal approaches for understanding complex data. A pivotal aspect of clustering analysis is quantitatively comparing clusterings; clustering comparison is the basis for many tasks such as clustering evaluation, consensus clustering, and tracking the temporal evolution of clusters. In p…
Unified framework for multi-user bandits using Laplacian kernels.
problem Multi-user contextual bandits with graph-related users and non-linear rewards.
method Joint penalty combining graph smoothness and individual roughness in a unified RKHS.
result Unified multi-user RKHS and effective dimension for regret bounds.
PolyNSD improves Neural Sheaf Diffusion with polynomial operators and spectral rescaling.
problem Limitations of common Neural Sheaf Diffusion implementations, including scalability and stability issues.
method Introduces Polynomial Neural Sheaf Diffusion (PolyNSD) with a degree-K polynomial propagation operator and spectral rescaling.
result PolyNSD achieves state-of-the-art results on both homophilic and heterophilic benchmarks with reduced runtime and memory requirements.
Mastering the dynamics of social influence requires separating, in a database of information propagation traces, the genuine causal processes from temporal correlation, i.e., homophily and other spurious causes. However, most studies to characterize social influence, and, in general, most data-science analyses focus on…
New framework detects outliers in non-IID categorical data.
problem Existing outlier detection methods fail in non-IID data.
method Value-value graph-based representation and outlierness propagation.
result Significant improvement in AUC on complex data sets.