Scholarlink

<p>Graph Neural Networks (GNNs) struggle on heterophilous graphs where edges connect dissimilar nodes. Existing rewiring methods increase homophily via heuristics without theoretical guarantees, fundamentally transforming graph character. We propose LIGR (Label Informativeness-Guided Rewiring), which maximizes an information-theoretic measure quantifying how much neighbors’ labels reveal about node labels. Building on the theoretical framework of LIMO et&#xa0;al. (<CitationRef CitationID="CR4">2025</CitationRef>), we extend the binary-class threshold analysis to multi-class settings, establish provable conditions for beneficial edge modifications, and prove convergence guarantees. Experiments on 9 benchmarks across three GNN architectures (GCN, GraphSAGE, GAT) show consistent improvements, with LIGR achieving best average performance and excelling particularly on citation networks (Cora: +6.5%, CiteSeer: +5.6%, PubMed: +5.3% with GCN). LIGR preserves graph structure without explicit constraints. Ablations confirm identical homophily changes with/without constraints, showing preservation is inherent to information-theoretic optimization. LIGR induces substantially less structural change than homophily-maximizing methods (average <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(|\Delta h| = 0.029\)</EquationSource> </InlineEquation> vs. 0.071–0.080) while maintaining competitive accuracy, suitable for applications requiring interpretability (biological networks, social graphs). Code: <a href="https://github.com/smlab-niser/ligr">https://github.com/smlab-niser/ligr</a>.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

LIGR: Label Informativeness-guided Graph Rewiring

  • 期刊论文

  • 发表日期：

    2026年7月3日

查看全文
  • Rucha Bhalchandra Joshi,
  • Subhankar Mishra

摘要

Graph Neural Networks (GNNs) struggle on heterophilous graphs where edges connect dissimilar nodes. Existing rewiring methods increase homophily via heuristics without theoretical guarantees, fundamentally transforming graph character. We propose LIGR (Label Informativeness-Guided Rewiring), which maximizes an information-theoretic measure quantifying how much neighbors’ labels reveal about node labels. Building on the theoretical framework of LIMO et al. (2025), we extend the binary-class threshold analysis to multi-class settings, establish provable conditions for beneficial edge modifications, and prove convergence guarantees. Experiments on 9 benchmarks across three GNN architectures (GCN, GraphSAGE, GAT) show consistent improvements, with LIGR achieving best average performance and excelling particularly on citation networks (Cora: +6.5%, CiteSeer: +5.6%, PubMed: +5.3% with GCN). LIGR preserves graph structure without explicit constraints. Ablations confirm identical homophily changes with/without constraints, showing preservation is inherent to information-theoretic optimization. LIGR induces substantially less structural change than homophily-maximizing methods (average \(|\Delta h| = 0.029\) vs. 0.071–0.080) while maintaining competitive accuracy, suitable for applications requiring interpretability (biological networks, social graphs). Code: https://github.com/smlab-niser/ligr.