This paper introduces a unified framework for extending optimal flow attributions to discrete structured data, such as graphs and text, through a novel formulation combining maximum flow algorithms with structured relaxation techniques. The proposed methods, Graph Flow Attribution (GFA) and Token Flow Attribution (TFA), provide theoretically-grounded attribution scores that satisfy properties like sensitivity, implementation invariance, and completeness.
Key findings
Proposes a unified framework for extending optimal flow attributions to discrete structured data.
Introduces Graph Flow Attribution (GFA) for attributing node and edge importance in graph neural networks.
Proposes Token Flow Attribution (TFA) for text attribution respecting token dependencies.
Theoretical properties of the methods include sensitivity, completeness, and computational complexity.
A comprehensive experimental plan is presented for evaluating discrete flow attribution methods.
Limitations & open questions
The paper does not yet include results from the comprehensive experimental plan.
Implementation constraints and potential failure modes are identified but not fully mitigated.